From 6f589fedcc826b125884e3a5884c9791802afb7f Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 00:23:59 +0100
Subject: add fuzzy mode

---
 background_page.html |  55 ++++++++-
 commands.js          |   9 +-
 fuzzyMode.js         | 166 ++++++++++++++++++++++++++
 lib/completion.js    | 324 +++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/keyboardUtils.js |   3 +-
 lib/utils.js         |  67 ++++++++---
 manifest.json        |   3 +
 vimium.css           |  70 +++++++++++
 8 files changed, 676 insertions(+), 21 deletions(-)
 create mode 100644 fuzzyMode.js
 create mode 100644 lib/completion.js

diff --git a/background_page.html b/background_page.html
index d8d3f75b..bca446a6 100644
--- a/background_page.html
+++ b/background_page.html
@@ -26,7 +26,9 @@
     returnScrollPosition: handleReturnScrollPosition,
     getCurrentTabUrl:     getCurrentTabUrl,
     settings:             handleSettings,
-    getBookmarks:         getBookmarks
+    getBookmarks:         getBookmarks,
+    getAllBookmarks:      getAllBookmarks,
+    getHistory:           getHistory,
   };
 
   var sendRequestHandlers = {
@@ -276,6 +278,57 @@
     })
   }
 
+  function getAllBookmarks(args, port) {
+    function traverseTree(bookmarks, callback) {
+      for (var i = 0; i < bookmarks.length; ++i) {
+        callback(bookmarks[i]);
+        if (typeof bookmarks[i].children === "undefined")
+          continue;
+        traverseTree(bookmarks[i].children, callback);
+      }
+    };
+
+    chrome.bookmarks.getTree(function(bookmarks) {
+      var results = [];
+      traverseTree(bookmarks, function(bookmark) {
+        if (typeof bookmark.url === "undefined")
+          return;
+        results.push(bookmark);
+      });
+      port.postMessage({bookmarks:results});
+    });
+  };
+
+  function getHistory(args, port) {
+    chrome.history.search({ text: '',
+                            maxResults: args.maxResults || 1000 },
+                      function(history) {
+      // sort by visit cound descending
+      history.sort(function(a, b) {
+        // visitCount may be undefined
+        var visitCountForA = a.visitCount || 0;
+        var visitCountForB = a.visitCount || 0;
+        return visitCountForB - visitCountForA;
+      });
+      var results = [];
+      for (var i = 0; i < history.length; ++i) {
+        results.push(history[i]);
+      }
+      port.postMessage({history:results});
+    });
+  };
+
+  /*
+   * Used by everyone to get settings from local storage.
+   */
+  function getSettingFromLocalStorage(setting) {
+    if (localStorage[setting] != "" && !localStorage[setting]) {
+      return defaultSettings[setting];
+    } else {
+      return localStorage[setting];
+    }
+  }
+
   function getCurrentTimeInSeconds() { Math.floor((new Date()).getTime() / 1000); }
 
   chrome.tabs.onSelectionChanged.addListener(function(tabId, selectionInfo) {
diff --git a/commands.js b/commands.js
index c961a901..1c19e26a 100644
--- a/commands.js
+++ b/commands.js
@@ -144,7 +144,10 @@ function clearKeyMappingsAndSetDefaults() {
     "b": "activateBookmarkFindMode",
     "B": "activateBookmarkFindModeToOpenInNewTab",
 
-    "gf": "nextFrame"
+    "o": "fuzzyMode.activate",
+    "O": "fuzzyMode.activateNewTab",
+
+    "gf": "nextFrame",
   };
 
   for (var key in defaultKeyMappings)
@@ -211,6 +214,9 @@ var commandDescriptions = {
   activateBookmarkFindMode: ["Open a bookmark in the current tab"],
   activateBookmarkFindModeToOpenInNewTab: ["Open a bookmark in a new tab"],
 
+  'fuzzyMode.activate': ["Open URL, bookmark, history entry or a custom search (fuzzy)"],
+  'fuzzyMode.activateNewTab': ["Open URL, bookmark, history entry or a custom search (fuzzy, new tab)"],
+
   nextFrame: ["Cycle forward to the next frame on the page", { background: true, passCountToFunction: true }]
 };
 
@@ -230,6 +236,7 @@ var commandGroups = {
      "enterInsertMode", "focusInput",
      "linkHints.activateMode", "linkHints.activateModeToOpenInNewTab", "linkHints.activateModeWithQueue",
      "activateBookmarkFindMode", "activateBookmarkFindModeToOpenInNewTab",
+     "fuzzyMode.activate", "fuzzyMode.activateNewTab",
      "goPrevious", "goNext", "nextFrame"],
   findCommands: ["enterFindMode", "performFind", "performBackwardsFind"],
   historyNavigation:
diff --git a/fuzzyMode.js b/fuzzyMode.js
new file mode 100644
index 00000000..ec2e351b
--- /dev/null
+++ b/fuzzyMode.js
@@ -0,0 +1,166 @@
+var fuzzyMode = (function() {
+  /** Trigger the fuzzy mode dialog */
+  var fuzzyBox = null;
+  function start(newTab) {
+    if (!fuzzyBox) {
+      var completer = new completion.MergingCompleter([
+        new completion.SmartCompleter(),
+        new completion.FuzzyHistoryCompleter(1000),
+        new completion.FuzzyBookmarkCompleter(),
+      ]);
+      fuzzyBox = new FuzzyBox(completer);
+    }
+    fuzzyBox.show(newTab);
+  }
+
+  /** User interface for fuzzy completion */
+  var FuzzyBox = function(completer, reverseAction) {
+    this.prompt = '> ';
+    this.completer = completer;
+    this.initDom();
+    this.reset();
+  }
+  FuzzyBox.prototype = {
+    show: function(reverseAction) {
+      this.reverseAction = reverseAction;
+      this.completer.refresh();
+      this.update();
+      this.box.style.display = 'block';
+      var self = this;
+      handlerStack.push({ keydown: function(event) { self.onKeydown(event); }});
+    },
+
+    hide: function() {
+      this.box.style.display = 'none';
+      handlerStack.pop();
+    },
+
+    reset: function() {
+      this.query = '';
+      this.completions = [];
+      this.selection = 0;
+      this.update();
+    },
+
+    updateSelection: function() {
+      var items = this.completionList.childNodes;
+      for (var i = 0; i < items.length; ++i) {
+        items[i].className = (i == this.selection) ? 'selected' : '';
+      }
+    },
+
+    onKeydown: function(event) {
+      var keyChar = getKeyChar(event);
+
+      if (isEscape(event)) {
+        this.hide();
+      }
+
+      // move selection with Up/Down, Tab/Shift-Tab, Ctrl-k/Ctrl-j
+      else if (keyChar === 'up' || (event.keyCode == 9 && event.shiftKey)
+              || (keyChar === 'k' && event.ctrlKey)) {
+        if (this.selection > 0)
+          this.selection -= 1;
+        this.updateSelection();
+      }
+      else if (keyChar === 'down' || (event.keyCode == 9 && !event.shiftKey)
+              || (keyChar === 'j' && isPrimaryModifierKey(event))) {
+        if (this.selection < this.completions.length - 1)
+          this.selection += 1;
+        this.updateSelection();
+      }
+
+      else if (event.keyCode == keyCodes.backspace) {
+        if (this.query.length > 0) {
+          this.query = this.query.substr(0, this.query.length-1);
+          this.update();
+        }
+      }
+
+      // use primary action with Enter. Holding down Shift/Ctrl uses the alternative action
+      // (opening in new tab)
+      else if (event.keyCode == keyCodes.enter) {
+        var alternative = (event.shiftKey || isPrimaryModifierKey(event));
+        if (this.reverseAction)
+          alternative = !alternative;
+        this.completions[this.selection].action[alternative ? 1 : 0]();
+        this.hide();
+        this.reset();
+      }
+
+      else if (keyChar.length == 1) {
+        this.query += keyChar;
+        this.update();
+      }
+
+      event.stopPropagation();
+      event.preventDefault();
+      return true;
+    },
+
+    update: function() {
+      this.query = this.query.replace(/^\s*/, '');
+      this.input.textContent = this.query;
+
+      // clear completions
+      this.completions = [];
+      while (this.completionList.hasChildNodes())
+        this.completionList.removeChild(this.completionList.firstChild);
+
+      if (this.query.length == 0) {
+        this.completionList.style.display = 'none';
+        return;
+      }
+
+      this.completionList.style.display = 'block';
+
+      var li;
+      var counter = 0;
+      var self = this;
+      this.completer.filter(this.query, function(completion) {
+        self.completions.push(completion);
+        li = document.createElement('li');
+        li.innerHTML = completion.render();
+        self.completionList.appendChild(li);
+        return ++counter < 10;
+      });
+
+      this.updateSelection();
+    },
+
+    initDom: function() {
+      this.box = document.createElement('div');
+      this.box.id = 'fuzzybox';
+      this.box.className = 'vimiumReset';
+
+      var inputBox = document.createElement('div');
+      inputBox.className = 'input';
+
+      var promptSpan = document.createElement('span');
+      promptSpan.className = 'prompt';
+      promptSpan.textContent = this.prompt;
+
+      this.input = document.createElement('span');
+      this.input.className = 'query';
+
+      inputBox.appendChild(promptSpan);
+      inputBox.appendChild(this.input);
+
+      this.completionList = document.createElement('ul');
+
+      this.box.appendChild(inputBox);
+      this.box.appendChild(this.completionList);
+
+      this.hide();
+      document.body.appendChild(this.box);
+    },
+  }
+
+  // public interface
+  return {
+    activate:       function() { start(false); },
+    activateNewTab: function() { start(true);  },
+  }
+
+})();
+
diff --git a/lib/completion.js b/lib/completion.js
new file mode 100644
index 00000000..cad7d455
--- /dev/null
+++ b/lib/completion.js
@@ -0,0 +1,324 @@
+var completion = (function() {
+
+  //============ Helper functions and objects ============//
+
+  /** Singleton object that provides helpers and caching for fuzzy completion. */
+  var fuzzyMatcher = (function() {
+    var self = {};
+
+    self.matcherCacheSize = 300;
+    self.regexNonWord = /\W*/g;
+
+    // cache generated regular expressions
+    self.matcherCache = {};
+    // cache filtered results from recent queries
+    self.filterCache = {};
+
+    /** Normalizes the string specified in :query. Strips any non-word characters and converts
+      * to lower case. */
+    self.normalize = function(query) {
+      return query.replace(self.regexNonWord, '').toLowerCase();
+    }
+
+    /** Calculates a very simple similarity value between a :query and a :string. The current
+      * implementation simply returns the length of the longest prefix of :query that is found within :str.
+      */
+    self.calculateRelevancy = function(query, str) {
+      query = self.normalize(query);
+      str   = self.normalize(str);
+      for (var i = query.length; i >= 0; --i) {
+        if (str.indexOf(query.slice(0, i)) >= 0)
+          return i;
+      }
+      return 0;
+    }
+
+    /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
+    self.cleanMatcherCache = function() {
+      // remove old matchers
+      queries = Object.keys(self.matcherCache);
+      for (var i = 0; i < queries.length - self.matcherCacheSize; ++i)
+        delete self.matcherCache(queries[i]);
+    }
+
+    /** Returns a regex that matches a string using a fuzzy :query. Example: The :query "abc" would result
+      * in a regex like /^([^a])*(a)([^b])*(b)([^c])*(c)(.*)$/
+      */
+    self.getMatcher = function(query) {
+      query = self.normalize(query);
+      if (!(query in self.matcherCache)) {
+        // build up a regex for fuzzy matching
+        var regex = '^';
+        for (var i = 0; i < query.length; ++i)
+          regex += '([^' + query[i] + ']*)(' + query[i] + ')';
+        self.matcherCache[query] = new RegExp(regex + '(.*)$', 'i');
+      }
+      return self.matcherCache[query];
+    }
+
+    /** Clears the filter cache with the given ID. */
+    self.clearFilterCache = function(id) {
+      if (id in self.filterCache)
+        delete self.filterCache[id];
+    }
+
+    /** Filters a list :ary using fuzzy matching against an input string :query. If a query with a less
+      * specific query was issued before (e.g. if the user added a letter to the query), the cached results
+      * of the last filtering are used as a starting point, instead of :ary.
+      */
+    self.filter = function(query, ary, getValue, id, callback) {
+      var filtered = [];
+      var source = ary;
+
+      if (!(id in self.filterCache))
+        self.filterCache[id] = {};
+
+      // find the most specific list of sources in the cache
+      var maxSpecificity = 0;
+      for (key in self.filterCache[id]) {
+        if (!self.filterCache[id].hasOwnProperty(key))
+          continue;
+
+        if ((query.indexOf(key) != 0 && key.indexOf(query) != 0) || key.length > query.length) {
+          // cache entry no longer needed
+          delete self.filterCache[id][key];
+          continue;
+        }
+
+        // is this cache entry the most specific so far?
+        var specificity = self.filterCache[id][key].length;
+        if (query.indexOf(key) == 0 && specificity > maxSpecificity) {
+          source = self.filterCache[id][key];
+          maxSpecificity = specificity;
+        }
+      }
+
+      // clean up
+      self.cleanMatcherCache();
+
+      var matcher = self.getMatcher(query);
+      for (var i = 0; i < source.length; ++i) {
+        if (!matcher.test(getValue(source[i])))
+          continue;
+        filtered.push(source[i]);
+        callback(source[i]);
+      }
+      self.filterCache[id][query] = filtered;
+    }
+
+    return self;
+  })();
+
+  /** Creates an action that opens :url in the current tab by default or in a new tab as an alternative. */
+  function createActionOpenUrl(url) {
+    return [
+      function() { window.location = url; },
+      function() { window.open(url); },
+    ]
+  }
+
+  /** Creates a completion that renders by marking fuzzy-matched parts. */
+  function createHighlightingCompletion(query, str, action, relevancy) {
+    return {
+      render: function() {
+        var match = fuzzyMatcher.getMatcher(query).exec(str);
+        var html = '';
+        for (var i = 1; i < match.length; ++i) {
+          if (i % 2 == 1)
+            html += match[i];
+          else
+            html += '<strong>' + match[i] + '</strong>';
+        };
+        return html;
+      },
+      action: action,
+      relevancy: relevancy,
+    }
+  }
+
+  /** Helper class to construct fuzzy completers for asynchronous data sources like history or bookmark
+   * matchers. */
+  var AsyncFuzzyUrlCompleter = function() {
+    this.completions = null;
+    this.id = utils.createUniqueId();
+    this.readyCallback = function(results) {
+      this.completions = results;
+    }
+  }
+  AsyncFuzzyUrlCompleter.prototype = {
+    // to be implemented by subclasses
+    refresh: function() { },
+
+    calculateRelevancy: function(query, match) {
+      return match.url.length * 10 / (fuzzyMatcher.calculateRelevancy(query, match.str)+1);
+    },
+
+    filter: function(query, callback) {
+      var self = this;
+
+      var handler = function(results) {
+        var filtered = [];
+        fuzzyMatcher.filter(query,
+                            self.completions, function(comp) { return comp.str },
+                            self.id,
+                            function(match) {
+          filtered.push(createHighlightingCompletion(
+                query, match.str,
+                createActionOpenUrl(match.url),
+                self.calculateRelevancy(query, match)));
+        });
+        callback(filtered);
+      }
+
+      // are the results ready?
+      if (this.completions !== null) {
+        // yes: call the callback synchronously
+        handler(this.completions);
+      } else {
+        // no: push our handler to the handling chain
+        var oldReadyCallback = this.readyCallback;
+        this.readyCallback = function(results) {
+          handler(results);
+          this.readyCallback = oldReadyCallback;
+          oldReadyCallback(results);
+        }
+      }
+    },
+  }
+
+  //========== Completer implementations ===========//
+
+  /** A simple completer that suggests to open the input string as an URL or to trigger a web search for the
+   * given term, depending on whether it thinks the input is an URL or not. */
+  var SmartCompleter = function() {
+    this.refresh = function() { };
+
+    this.filter = function(query, callback) {
+      var url;
+      var str;
+
+      if (utils.isUrl(query)) {
+        url = utils.createFullUrl(query);
+        str = '<em>goto</em> ' + url;
+      } else {
+        url = utils.createSearchUrl(query);
+        str = '<em>search</em> ' + query;
+      }
+
+      // call back with exactly one suggestion
+      callback([{
+        render: function() { return str; },
+        action: createActionOpenUrl(url),
+        // relevancy will always be the lowest one, so the suggestion is at the top
+        relevancy: -1,
+      }]);
+    };
+  }
+
+  /** A fuzzy history completer */
+  var FuzzyHistoryCompleter = function(maxEntries) {
+    AsyncFuzzyUrlCompleter.call(this);
+    this.maxEntries = maxEntries || 1000;
+  }
+  FuzzyHistoryCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  FuzzyHistoryCompleter.prototype.refresh = function() {
+    this.completions = null; // reset completions
+
+    // asynchronously fetch history items
+    var port = chrome.extension.connect({ name: "getHistory" }) ;
+    var self = this;
+    port.onMessage.addListener(function(msg) {
+      var results = [];
+
+      for (var i = 0; i < msg.history.length; ++i) {
+        var historyItem = msg.history[i];
+        var title = '';
+
+        if (historyItem.title.length > 0)
+          title = ' (' + historyItem.title + ')';
+
+        results.push({
+          str: 'history: ' + historyItem.url + title,
+          url: historyItem.url,
+        });
+      }
+      port = null;
+      self.readyCallback(results);
+    });
+    port.postMessage({ maxResults: this.maxEntries });
+  }
+
+  /** A fuzzy bookmark completer */
+  var FuzzyBookmarkCompleter = function() {
+    AsyncFuzzyUrlCompleter.call(this);
+  }
+  FuzzyBookmarkCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  FuzzyBookmarkCompleter.prototype.refresh = function() {
+    this.completions = null; // reset completions
+
+    var port = chrome.extension.connect({ name: "getAllBookmarks" }) ;
+    var self = this;
+    port.onMessage.addListener(function(msg) {
+      var results = [];
+
+      for (var i = 0; i < msg.bookmarks.length; ++i) {
+        var bookmark = msg.bookmarks[i];
+
+        var title = '';
+        if (bookmark.title.length > 0)
+          title = ' (' + bookmark.title + ')';
+
+        results.push({
+          str: 'bookmark: ' + bookmark.url + title,
+          url: bookmark.url,
+        });
+      }
+      port = null;
+      self.readyCallback(results);
+    });
+    port.postMessage();
+  }
+
+  /** A meta-completer that delegates queries and merges and sorts the results of a collection of other
+   * completer instances. */
+  var MergingCompleter = function(sources) {
+    this.sources = sources;
+  }
+  MergingCompleter.prototype = {
+    refresh: function() {
+      for (var i = 0; i < this.sources.length; ++i)
+        this.sources[i].refresh();
+    },
+
+    filter: function(query, callback) {
+      var all = [];
+      var counter = this.sources.length;
+
+      for (var i = 0; i < this.sources.length; ++i) {
+        this.sources[i].filter(query, function(results) {
+          all = all.concat(results);
+          if (--counter > 0)
+            return;
+
+          // all sources have provided results by now, so we can sort and return
+          all.sort(function(a,b) {
+            return a.relevancy - b.relevancy;
+          });
+          for (var i = 0; i < all.length; ++i) {
+            if (!callback(all[i]))
+              // the caller doesn't want any more results
+              return;
+          }
+        });
+      }
+    }
+  }
+
+  // public interface
+  return {
+    FuzzyHistoryCompleter: FuzzyHistoryCompleter,
+    FuzzyBookmarkCompleter: FuzzyBookmarkCompleter,
+    SmartCompleter: SmartCompleter,
+    MergingCompleter: MergingCompleter,
+  };
+})();
diff --git a/lib/keyboardUtils.js b/lib/keyboardUtils.js
index 98725d95..84e860ba 100644
--- a/lib/keyboardUtils.js
+++ b/lib/keyboardUtils.js
@@ -47,7 +47,8 @@ function getKeyChar(event) {
       keyIdentifier = event.shiftKey ? correctedIdentifiers[1] : correctedIdentifiers[0];
     }
     var unicodeKeyInHex = "0x" + keyIdentifier.substring(2);
-    return String.fromCharCode(parseInt(unicodeKeyInHex)).toLowerCase();
+    var character = String.fromCharCode(parseInt(unicodeKeyInHex)).toLowerCase();
+    return event.shiftKey ? character.toUpperCase() : character;
 }
 
 function isPrimaryModifierKey(event) {
diff --git a/lib/utils.js b/lib/utils.js
index 8aada3a1..922e7db3 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -21,17 +21,26 @@ var utils = {
   },
 
   /**
-   * Creates a search URL from the given :query.
+   * Generates a unique ID
    */
-  createSearchUrl: function(query) {
-    return "http://www.google.com/search?q=" + query;
+  createUniqueId: (function() {
+    id = 0;
+    return function() { return ++id; };
+  })(),
+
+  /**
+   * Completes a partial URL (without scheme)
+   */
+  createFullUrl: function(partialUrl) {
+    if (!/^[a-z]{3,}:\/\//.test(partialUrl))
+      partialUrl = 'http://' + partialUrl;
+    return partialUrl
   },
 
   /**
-   * Tries to convert :str into a valid URL.
-   * We don't bother with escaping characters, however, as Chrome will do that for us.
+   * Tries to detect, whether :str is a valid URL.
    */
-  ensureUrl: function(str) {
+  isUrl: function(str) {
     // more or less RFC compliant URL host part parsing. This should be sufficient
     // for our needs
     var urlRegex = new RegExp(
@@ -55,38 +64,60 @@ var utils = {
 
     // it starts with a scheme, so it's definitely an URL
     if (/^[a-z]{3,}:\/\//.test(str))
-      return str;
-    var strWithScheme = 'http://' + str;
+      return true;
 
-    // definitely not a valid URL; treat as search query
+    // spaces => definitely not a valid URL
     if (str.indexOf(' ') >= 0)
-      return utils.createSearchUrl(str);
+      return false;
 
     // assuming that this is an URL, try to parse it into its meaningful parts. If matching fails, we're
     // pretty sure that we don't have some kind of URL here.
     var match = urlRegex.exec(str.split('/')[0]);
     if (!match)
-      return utils.createSearchUrl(str);
+      return false;
     var hostname = match[3];
 
     // allow known special host names
     if (specialHostNames.indexOf(hostname) >= 0)
-      return strWithScheme;
+      return true;
 
     // allow IPv6 addresses (need to be wrapped in brackets, as required by RFC).  It is sufficient to check
     // for a colon here, as the regex wouldn't match colons in the host name unless it's an v6 address
     if (hostname.indexOf(':') >= 0)
-      return strWithScheme;
+      return true;
 
     // at this point we have to make a decision. As a heuristic, we check if the input has dots in it. If
-    // yes, and if the last part could be a TLD, treat it as an URL
+    // yes, and if the last part could be a TLD, treat it as an URL.
     var dottedParts = hostname.split('.');
     var lastPart = dottedParts[dottedParts.length-1];
-    if (dottedParts.length > 1 && (lastPart.length <= 3 || longTlds.indexOf(lastPart) >= 0))
-      return strWithScheme;
+    if (dottedParts.length > 1 && ((lastPart.length >= 2 && lastPart.length <= 3)
+                                   || longTlds.indexOf(lastPart) >= 0))
+      return true;
+
+    // also allow IPv4 addresses
+    if (/^(\d{1,3}\.){3}\d{1,3}$/.test(hostname))
+      return true;
+
+    // fallback: no URL
+    return false
+  },
 
-    // fallback: use as search query
-    return utils.createSearchUrl(str);
+  /**
+   * Creates a search URL from the given :query.
+   */
+  createSearchUrl: function(query) {
+    return "http://www.google.com/search?q=" + query;
+  },
+
+  /**
+   * Tries to convert :str into a valid URL.
+   * We don't bother with escaping characters, however, as Chrome will do that for us.
+   */
+  ensureUrl: function(str) {
+    if (utils.isUrl(str))
+      return utils.createFullUrl(str);
+    else
+      return utils.createSearchUrl(str);
   },
 
 };
diff --git a/manifest.json b/manifest.json
index 72631a94..a14e2fef 100644
--- a/manifest.json
+++ b/manifest.json
@@ -10,6 +10,7 @@
   "permissions": [
     "tabs",
     "bookmarks",
+    "history",
     "clipboardRead",
     "<all_urls>"
   ],
@@ -20,7 +21,9 @@
              "lib/keyboardUtils.js",
              "lib/domUtils.js",
              "lib/clipboard.js",
+             "lib/completion.js",
              "linkHints.js",
+             "fuzzyMode.js",
              "vimiumFrontend.js",
              "completionDialog.js",
              "bookmarks.js"
diff --git a/vimium.css b/vimium.css
index ef33428c..35a4473b 100644
--- a/vimium.css
+++ b/vimium.css
@@ -282,4 +282,74 @@ div.vimium-completions div.vimium-noResults{
 
 body.vimiumFindMode ::selection {
   background: #ff9632;
+};
+
+/* fuzzymode CSS */
+
+#fuzzybox ol, #fuzzybox ul {
+  list-style: none;
+}
+
+#fuzzybox {
+  position: fixed;
+  width: 80%;
+  top: 70px;
+  left: 50%;
+  margin: 0 0 0 -40%;
+  background: black;
+  color: white;
+  font-family: sans-serif;
+  font-size: 30px;
+  text-align: left;
+  padding: 7px 20px 7px 20px;
+  opacity: 0.9;
+  border-radius: 10px;
+  box-shadow: 5px 5px 5px rgba(0,0,0,0.5);
+  z-index: 99999998;
+}
+
+#fuzzybox ul {
+  list-style: none;
+  padding: 7px 0 0 0;
+  margin: 7px 0 0 0;
+  border-top: 2px solid #444;
+}
+
+#fuzzybox li {
+  border-bottom: 1px solid #111;
+  line-height: 1.1em;
+  padding: 7px;
+  margin: 0 -7px 0 -7px;
+  font-size: 18px;
+  color: #aaa;
+}
+
+#fuzzybox li strong {
+  color: red;
+}
+
+#fuzzybox li em {
+  color: #444;
+  font-weight: normal;
+  font-style: italic;
+}
+
+#fuzzybox li.selected {
+  background: #222;
+  color: #ccc;
+  border-radius: 4px;
+}
+#fuzzybox li.selected em {
+  color: #666;
+}
+
+#fuzzybox .input {
+  font-size: 28px;
+  padding: 0;
+  margin: 0;
+}
+
+#fuzzybox .input .prompt {
+  color: orange;
+  content: '>> ';
 }
-- 
cgit v1.2.3


From fd549f0385bf37bf4715c14c85db842954038106 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 00:26:03 +0100
Subject: make failing test pass again :)

---
 lib/utils.js | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/utils.js b/lib/utils.js
index 922e7db3..e23799d8 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -114,6 +114,8 @@ var utils = {
    * We don't bother with escaping characters, however, as Chrome will do that for us.
    */
   ensureUrl: function(str) {
+    // trim str
+    str = str.replace(/^\s+|\s+$/g, '');
     if (utils.isUrl(str))
       return utils.createFullUrl(str);
     else
-- 
cgit v1.2.3


From c808c6a165b5fed117afe22ba0372e288bf6d5ab Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 00:34:25 +0100
Subject: remove trimming from isUrl

---
 lib/completion.js | 2 ++
 lib/utils.js      | 6 ------
 2 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index cad7d455..75785c34 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -197,6 +197,8 @@ var completion = (function() {
       var url;
       var str;
 
+      // trim query
+      query = query.replace(/^\s+|\s+$/g, '');
       if (utils.isUrl(query)) {
         url = utils.createFullUrl(query);
         str = '<em>goto</em> ' + url;
diff --git a/lib/utils.js b/lib/utils.js
index e23799d8..2b580786 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -56,12 +56,6 @@ var utils = {
     // are there more?
     var specialHostNames = [ 'localhost' ];
 
-    // trim str
-    str = str.replace(/^\s+|\s+$/g, '');
-
-    if (str[0] === '/')
-      return "file://" + str;
-
     // it starts with a scheme, so it's definitely an URL
     if (/^[a-z]{3,}:\/\//.test(str))
       return true;
-- 
cgit v1.2.3


From 253dc6f55885dd0185ab5b061ec2d9429c729ed9 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 01:31:18 +0100
Subject: add possibility to use custom search engines and use "wiki ", "cc ",
 and ";" (goto) as custom commands

---
 fuzzyMode.js      |  6 +++++-
 lib/completion.js | 51 ++++++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 47 insertions(+), 10 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index ec2e351b..0387e97b 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -4,7 +4,11 @@ var fuzzyMode = (function() {
   function start(newTab) {
     if (!fuzzyBox) {
       var completer = new completion.MergingCompleter([
-        new completion.SmartCompleter(),
+        new completion.SmartCompleter({
+          'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
+          'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
+          ';'    : [ 'goto',           '%s' ]
+        }),
         new completion.FuzzyHistoryCompleter(1000),
         new completion.FuzzyBookmarkCompleter(),
       ]);
diff --git a/lib/completion.js b/lib/completion.js
index 75785c34..f713eaa0 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -136,6 +136,11 @@ var completion = (function() {
     }
   }
 
+  /** Creates a function that returns a constant value */
+  function createConstantFunction(x) {
+    return function() { return x; }
+  }
+
   /** Helper class to construct fuzzy completers for asynchronous data sources like history or bookmark
    * matchers. */
   var AsyncFuzzyUrlCompleter = function() {
@@ -190,30 +195,58 @@ var completion = (function() {
 
   /** A simple completer that suggests to open the input string as an URL or to trigger a web search for the
    * given term, depending on whether it thinks the input is an URL or not. */
-  var SmartCompleter = function() {
+  var SmartCompleter = function(commands) {
+    commands = commands || {};
+    var commandKeys = Object.keys(commands);
+
     this.refresh = function() { };
 
-    this.filter = function(query, callback) {
-      var url;
-      var str;
+    /** Checks if the input is a special command and if yes, add according suggestions to the given array */
+    this.addCommandSuggestions = function(query, suggestions) {
+      // check if the input is a special command
+      for (var i = 0; i < commandKeys.length; ++i) {
+        var key = commandKeys[i];
+        if (query.indexOf(key) != 0)
+          continue;
+
+        var term = query.slice(key.length, query.length);
+        var command = commands[key];
+        var desc = command[0];
+        var urlPattern = command[1];
+        suggestions.push({
+          render: createConstantFunction('<em>' + desc + '</em> ' + term),
+          action: createActionOpenUrl(utils.createFullUrl(urlPattern.replace(/%s/g, term))),
+        });
+      }
+    }
+
+    /** Checks if the input is a URL. If yes, add the URL to the list of suggestions. If no, add a search
+     * query to the list of suggestions. */
+    this.addUrlOrSearchSuggestion = function(query, suggestions) {
+      var url, str;
 
       // trim query
       query = query.replace(/^\s+|\s+$/g, '');
       if (utils.isUrl(query)) {
         url = utils.createFullUrl(query);
-        str = '<em>goto</em> ' + url;
+        str = '<em>goto</em> ' + query;
       } else {
         url = utils.createSearchUrl(query);
         str = '<em>search</em> ' + query;
       }
-
-      // call back with exactly one suggestion
-      callback([{
+      suggestions.push({
         render: function() { return str; },
         action: createActionOpenUrl(url),
         // relevancy will always be the lowest one, so the suggestion is at the top
         relevancy: -1,
-      }]);
+      });
+    }
+
+    this.filter = function(query, callback) {
+      var suggestions = [];
+      this.addCommandSuggestions(query, suggestions);
+      this.addUrlOrSearchSuggestion(query, suggestions);
+      callback(suggestions);
     };
   }
 
-- 
cgit v1.2.3


From f4416cb1e369f462aa83e9489de74f27bf330759 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 01:37:55 +0100
Subject: remove useless CSS directive

---
 vimium.css | 1 -
 1 file changed, 1 deletion(-)

diff --git a/vimium.css b/vimium.css
index 35a4473b..ebaa41d7 100644
--- a/vimium.css
+++ b/vimium.css
@@ -351,5 +351,4 @@ body.vimiumFindMode ::selection {
 
 #fuzzybox .input .prompt {
   color: orange;
-  content: '>> ';
 }
-- 
cgit v1.2.3


From 2a9c88ae1db8b4eadd5ad815966b1820c5d0af5b Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 01:41:14 +0100
Subject: make CSS more specific

---
 vimium.css | 77 +++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 39 insertions(+), 38 deletions(-)

diff --git a/vimium.css b/vimium.css
index ebaa41d7..e0aec149 100644
--- a/vimium.css
+++ b/vimium.css
@@ -287,68 +287,69 @@ body.vimiumFindMode ::selection {
 /* fuzzymode CSS */
 
 #fuzzybox ol, #fuzzybox ul {
-  list-style: none;
+  list-style: none !important;
 }
 
 #fuzzybox {
-  position: fixed;
-  width: 80%;
-  top: 70px;
-  left: 50%;
-  margin: 0 0 0 -40%;
-  background: black;
-  color: white;
-  font-family: sans-serif;
-  font-size: 30px;
-  text-align: left;
-  padding: 7px 20px 7px 20px;
-  opacity: 0.9;
-  border-radius: 10px;
-  box-shadow: 5px 5px 5px rgba(0,0,0,0.5);
-  z-index: 99999998;
+  position: fixed !important;
+  width: 80% !important;
+  top: 70px !important;
+  left: 50% !important;
+  margin: 0 0 0 -40% !important;
+  background: black !important;
+  color: white !important;
+  font-family: sans-serif !important;
+  font-size: 30px !important;
+  text-align: left !important;
+  padding: 7px 20px 7px 20px !important;
+  opacity: 0.9 !important;
+  border-radius: 10px !important;
+  box-shadow: 5px 5px 5px rgba(0,0,0,0.5) !important;
+  z-index: 99999998 !important;
 }
 
 #fuzzybox ul {
-  list-style: none;
-  padding: 7px 0 0 0;
-  margin: 7px 0 0 0;
-  border-top: 2px solid #444;
+  list-style: none !important;
+  padding: 7px 0 0 0 !important;
+  margin: 7px 0 0 0 !important;
+  border-top: 2px solid #444 !important;
 }
 
 #fuzzybox li {
-  border-bottom: 1px solid #111;
-  line-height: 1.1em;
-  padding: 7px;
-  margin: 0 -7px 0 -7px;
-  font-size: 18px;
-  color: #aaa;
+  border-bottom: 1px solid #111 !important;
+  line-height: 1.1em !important;
+  padding: 7px !important;
+  margin: 0 -7px 0 -7px !important;
+  font-size: 18px !important;
+  color: #aaa !important;
 }
 
 #fuzzybox li strong {
-  color: red;
+  color: red !important;
 }
 
 #fuzzybox li em {
-  color: #444;
-  font-weight: normal;
-  font-style: italic;
+  color: #444 !important;
+  font-weight: normal !important;
+  font-style: italic !important;
 }
 
 #fuzzybox li.selected {
-  background: #222;
-  color: #ccc;
-  border-radius: 4px;
+  background: #222 !important;
+  color: #ccc !important;
+  border-radius: 4px !important;
+  font-weight: normal !important;
 }
 #fuzzybox li.selected em {
-  color: #666;
+  color: #666 !important;
 }
 
 #fuzzybox .input {
-  font-size: 28px;
-  padding: 0;
-  margin: 0;
+  font-size: 28px !important;
+  padding: 0 !important;
+  margin: 0 !important;
 }
 
 #fuzzybox .input .prompt {
-  color: orange;
+  color: orange !important;
 }
-- 
cgit v1.2.3


From bd6f3bebc41792567b31804f3463119b649cb1e1 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 02:53:57 +0100
Subject: fix some issues with asynchronous filtering and refreshing

---
 fuzzyMode.js      | 32 ++++++++++++++------------------
 lib/completion.js | 17 ++++++-----------
 2 files changed, 20 insertions(+), 29 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 0387e97b..5588c281 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -9,6 +9,7 @@ var fuzzyMode = (function() {
           'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
           ';'    : [ 'goto',           '%s' ]
         }),
+        completer.refresh();
         new completion.FuzzyHistoryCompleter(1000),
         new completion.FuzzyBookmarkCompleter(),
       ]);
@@ -27,8 +28,6 @@ var fuzzyMode = (function() {
   FuzzyBox.prototype = {
     show: function(reverseAction) {
       this.reverseAction = reverseAction;
-      this.completer.refresh();
-      this.update();
       this.box.style.display = 'block';
       var self = this;
       handlerStack.push({ keydown: function(event) { self.onKeydown(event); }});
@@ -106,30 +105,27 @@ var fuzzyMode = (function() {
       this.query = this.query.replace(/^\s*/, '');
       this.input.textContent = this.query;
 
-      // clear completions
-      this.completions = [];
-      while (this.completionList.hasChildNodes())
-        this.completionList.removeChild(this.completionList.firstChild);
-
       if (this.query.length == 0) {
         this.completionList.style.display = 'none';
         return;
       }
-
       this.completionList.style.display = 'block';
 
-      var li;
-      var counter = 0;
       var self = this;
-      this.completer.filter(this.query, function(completion) {
-        self.completions.push(completion);
-        li = document.createElement('li');
-        li.innerHTML = completion.render();
-        self.completionList.appendChild(li);
-        return ++counter < 10;
+      this.completer.filter(this.query, function(completions) {
+        // clear completions
+        self.completions = [];
+        while (self.completionList.hasChildNodes())
+          self.completionList.removeChild(self.completionList.firstChild);
+
+        for (var i = 0; i < completions.length && i < 10; ++i) {
+          self.completions.push(completions[i]);
+          var li = document.createElement('li');
+          li.innerHTML = completions[i].render();
+          self.completionList.appendChild(li);
+        }
+        self.updateSelection();
       });
-
-      this.updateSelection();
     },
 
     initDom: function() {
diff --git a/lib/completion.js b/lib/completion.js
index f713eaa0..c7ac0417 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -146,7 +146,7 @@ var completion = (function() {
   var AsyncFuzzyUrlCompleter = function() {
     this.completions = null;
     this.id = utils.createUniqueId();
-    this.readyCallback = function(results) {
+    this.readyCallback = this.fallbackReadyCallback = function(results) {
       this.completions = results;
     }
   }
@@ -164,7 +164,7 @@ var completion = (function() {
       var handler = function(results) {
         var filtered = [];
         fuzzyMatcher.filter(query,
-                            self.completions, function(comp) { return comp.str },
+                            results, function(comp) { return comp.str },
                             self.id,
                             function(match) {
           filtered.push(createHighlightingCompletion(
@@ -180,12 +180,11 @@ var completion = (function() {
         // yes: call the callback synchronously
         handler(this.completions);
       } else {
-        // no: push our handler to the handling chain
-        var oldReadyCallback = this.readyCallback;
+        // no: register the handler as a callback
         this.readyCallback = function(results) {
           handler(results);
-          this.readyCallback = oldReadyCallback;
-          oldReadyCallback(results);
+          this.readyCallback = this.fallbackReadyCallback;
+          this.readyCallback(results);
         }
       }
     },
@@ -339,11 +338,7 @@ var completion = (function() {
           all.sort(function(a,b) {
             return a.relevancy - b.relevancy;
           });
-          for (var i = 0; i < all.length; ++i) {
-            if (!callback(all[i]))
-              // the caller doesn't want any more results
-              return;
-          }
+          callback(all);
         });
       }
     }
-- 
cgit v1.2.3


From b6a91ffacc26d752c9d387cc9c0251869b163f51 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 02:54:26 +0100
Subject: make F5 refresh the completions

---
 fuzzyMode.js | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 5588c281..f4ad082c 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -80,6 +80,12 @@ var fuzzyMode = (function() {
         }
       }
 
+      // refresh with F5
+      else if (keyChar == 'f5') {
+        this.completer.refresh();
+        this.update();
+      }
+
       // use primary action with Enter. Holding down Shift/Ctrl uses the alternative action
       // (opening in new tab)
       else if (event.keyCode == keyCodes.enter) {
-- 
cgit v1.2.3


From 9e6bdefd3d7815047c6d5f367370a19656e2da40 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 02:55:47 +0100
Subject: remove empty leading line

---
 fuzzyMode.js | 1 -
 1 file changed, 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index f4ad082c..6349999e 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -169,4 +169,3 @@ var fuzzyMode = (function() {
   }
 
 })();
-
-- 
cgit v1.2.3


From ef7084e915fb67d8cb52d29d1dfbb31ae185f666 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 03:25:22 +0100
Subject: fix syntax error

---
 fuzzyMode.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 6349999e..8c43cad0 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -9,10 +9,10 @@ var fuzzyMode = (function() {
           'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
           ';'    : [ 'goto',           '%s' ]
         }),
-        completer.refresh();
         new completion.FuzzyHistoryCompleter(1000),
         new completion.FuzzyBookmarkCompleter(),
       ]);
+      completer.refresh();
       fuzzyBox = new FuzzyBox(completer);
     }
     fuzzyBox.show(newTab);
-- 
cgit v1.2.3


From 79b0340f40149bafd48d3d23200c3e613068a9dc Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 03:51:17 +0100
Subject: allow fuzzy completion of HTML-decorated content and implement this
 for history and bookmarks

---
 lib/completion.js | 53 ++++++++++++++++++++++++++++++++++++++++++++---------
 vimium.css        | 15 +++++++++++----
 2 files changed, 55 insertions(+), 13 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index c7ac0417..2b29258f 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -109,6 +109,25 @@ var completion = (function() {
     return self;
   })();
 
+  /** Strips HTML tags using a naive regex replacement. Optinally, saves the stripped HTML tags in a
+   * dictionary indexed by the position where the tag should be reinserted. */
+  function stripHtmlTags(str, positions) {
+    var result = str.replace(/<[^>]*>/g, '');
+    if (!positions)
+      return result;
+
+    // we need to get information about where the tags can be reinserted after some string processing
+    var start;
+    var end = -1;
+    var stripped = 0;
+    while (0 <= (start = str.indexOf('<', end + 1))) {
+      end = str.indexOf('>', start);
+      positions[start - stripped] = str.slice(start, end + 1);
+      stripped += end - start + 1;
+    }
+    return result;
+  }
+
   /** Creates an action that opens :url in the current tab by default or in a new tab as an alternative. */
   function createActionOpenUrl(url) {
     return [
@@ -121,14 +140,30 @@ var completion = (function() {
   function createHighlightingCompletion(query, str, action, relevancy) {
     return {
       render: function() {
+        var htmlTags = {};
+        str = stripHtmlTags(str, htmlTags);
         var match = fuzzyMatcher.getMatcher(query).exec(str);
+        if (!match)
+          console.log(query, str);
         var html = '';
-        for (var i = 1; i < match.length; ++i) {
-          if (i % 2 == 1)
-            html += match[i];
+        var i = 0;
+
+        function addToHtml(str) {
+          if (i in htmlTags)
+            html += htmlTags[i];
+          html += str;
+          ++i;
+        }
+
+        for (var m = 1; m < match.length; ++m) {
+          if (m % 2 == 1)
+            for (var j = 0; j < match[m].length; ++j)
+              addToHtml(match[m][j]);
           else
-            html += '<strong>' + match[i] + '</strong>';
+            addToHtml('<span class="fuzzyMatch">' + match[m] + '</span>');
         };
+        addToHtml('');
+
         return html;
       },
       action: action,
@@ -164,7 +199,7 @@ var completion = (function() {
       var handler = function(results) {
         var filtered = [];
         fuzzyMatcher.filter(query,
-                            results, function(comp) { return comp.str },
+                            results, function(comp) { return stripHtmlTags(comp.str) },
                             self.id,
                             function(match) {
           filtered.push(createHighlightingCompletion(
@@ -269,10 +304,10 @@ var completion = (function() {
         var title = '';
 
         if (historyItem.title.length > 0)
-          title = ' (' + historyItem.title + ')';
+          title = ' <span class="title">' + historyItem.title + '</span>';
 
         results.push({
-          str: 'history: ' + historyItem.url + title,
+          str: '<em>history</em> ' + historyItem.url + title,
           url: historyItem.url,
         });
       }
@@ -300,10 +335,10 @@ var completion = (function() {
 
         var title = '';
         if (bookmark.title.length > 0)
-          title = ' (' + bookmark.title + ')';
+          title = ' <span class="title">' + bookmark.title + '</span>';
 
         results.push({
-          str: 'bookmark: ' + bookmark.url + title,
+          str: '<em>bookmark</em> ' + bookmark.url + title,
           url: bookmark.url,
         });
       }
diff --git a/vimium.css b/vimium.css
index e0aec149..5d0f69ad 100644
--- a/vimium.css
+++ b/vimium.css
@@ -321,18 +321,25 @@ body.vimiumFindMode ::selection {
   padding: 7px !important;
   margin: 0 -7px 0 -7px !important;
   font-size: 18px !important;
-  color: #aaa !important;
+  color: #ddd !important;
 }
 
-#fuzzybox li strong {
+#fuzzybox li .fuzzyMatch {
   color: red !important;
 }
 
-#fuzzybox li em {
+#fuzzybox li em, #fuzzybox li .title {
   color: #444 !important;
   font-weight: normal !important;
+}
+#fuzzybox li em {
   font-style: italic !important;
 }
+#fuzzybox li em .fuzzyMatch, #fuzzybox li .title .fuzzyMatch {
+  color: #888 !important;
+  font-style: inherit !important;
+  font-weight: bold !important;
+}
 
 #fuzzybox li.selected {
   background: #222 !important;
@@ -340,7 +347,7 @@ body.vimiumFindMode ::selection {
   border-radius: 4px !important;
   font-weight: normal !important;
 }
-#fuzzybox li.selected em {
+#fuzzybox li.selected em, #fuzzybox li.selected .title {
   color: #666 !important;
 }
 
-- 
cgit v1.2.3


From 69ea703f584f65c962fb04fcae7bb6500a11b76a Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 04:00:12 +0100
Subject: allow custom functions as commands, add example in form of forced web
 search

---
 fuzzyMode.js      |  3 ++-
 lib/completion.js | 11 +++++++++--
 2 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8c43cad0..a470bea9 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -7,7 +7,8 @@ var fuzzyMode = (function() {
         new completion.SmartCompleter({
           'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
           'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
-          ';'    : [ 'goto',           '%s' ]
+          ';'    : [ 'goto',           '%s' ],
+          '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         }),
         new completion.FuzzyHistoryCompleter(1000),
         new completion.FuzzyBookmarkCompleter(),
diff --git a/lib/completion.js b/lib/completion.js
index 2b29258f..6e8ea803 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -246,10 +246,17 @@ var completion = (function() {
         var term = query.slice(key.length, query.length);
         var command = commands[key];
         var desc = command[0];
-        var urlPattern = command[1];
+        var pattern = command[1];
+        var url;
+
+        if (typeof pattern === 'function')
+          url = pattern(term);
+        else
+          url = pattern.replace(/%s/g, term);
+
         suggestions.push({
           render: createConstantFunction('<em>' + desc + '</em> ' + term),
-          action: createActionOpenUrl(utils.createFullUrl(urlPattern.replace(/%s/g, term))),
+          action: createActionOpenUrl(utils.createFullUrl(url)),
         });
       }
     }
-- 
cgit v1.2.3


From 667f97b8d9efce79cb2f554079a79fadf81542ad Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 04:19:31 +0100
Subject: document the HTML matching algorithm better

---
 lib/completion.js | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 6e8ea803..0b4c5a0a 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -139,15 +139,20 @@ var completion = (function() {
   /** Creates a completion that renders by marking fuzzy-matched parts. */
   function createHighlightingCompletion(query, str, action, relevancy) {
     return {
+      action: action,
+      relevancy: relevancy,
+
       render: function() {
+        // we want to match the content in HTML tags, but not the HTML tags themselves, so we remove the
+        // tags and reinsert them after the matching process
         var htmlTags = {};
         str = stripHtmlTags(str, htmlTags);
         var match = fuzzyMatcher.getMatcher(query).exec(str);
-        if (!match)
-          console.log(query, str);
         var html = '';
         var i = 0;
 
+        // this helper function adds the HTML generated _for one single character_ to the HTML output
+        // and reinserts HTML tags stripped before, if they were at this position
         function addToHtml(str) {
           if (i in htmlTags)
             html += htmlTags[i];
@@ -155,19 +160,24 @@ var completion = (function() {
           ++i;
         }
 
+        // iterate over the match groups. They are non-matched and matched string parts, in alternating order
         for (var m = 1; m < match.length; ++m) {
           if (m % 2 == 1)
+            // we have a non-matched part, it could have several characters. We need to insert them character
+            // by character, so that addToHtml can keep track of the position in the original string
             for (var j = 0; j < match[m].length; ++j)
               addToHtml(match[m][j]);
           else
+            // we have a matched part, which consists of exactly one character. In addition to the character
+            // itself, we add some decorating HTML.
             addToHtml('<span class="fuzzyMatch">' + match[m] + '</span>');
         };
+
+        // call it another time so that a tag at the very last position is reinserted
         addToHtml('');
 
         return html;
       },
-      action: action,
-      relevancy: relevancy,
     }
   }
 
-- 
cgit v1.2.3


From 85ae8c6c17c3b83a7b3519844f01c7624e84f0e3 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 04:25:41 +0100
Subject: make number of completions configurable

---
 fuzzyMode.js | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index a470bea9..6e2867d2 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -14,14 +14,15 @@ var fuzzyMode = (function() {
         new completion.FuzzyBookmarkCompleter(),
       ]);
       completer.refresh();
-      fuzzyBox = new FuzzyBox(completer);
+      fuzzyBox = new FuzzyBox(completer, 10);
     }
     fuzzyBox.show(newTab);
   }
 
   /** User interface for fuzzy completion */
-  var FuzzyBox = function(completer, reverseAction) {
+  var FuzzyBox = function(completer, maxResults) {
     this.prompt = '> ';
+    this.maxResults = maxResults || 10;
     this.completer = completer;
     this.initDom();
     this.reset();
@@ -125,7 +126,7 @@ var fuzzyMode = (function() {
         while (self.completionList.hasChildNodes())
           self.completionList.removeChild(self.completionList.firstChild);
 
-        for (var i = 0; i < completions.length && i < 10; ++i) {
+        for (var i = 0; i < completions.length && i < self.maxResults; ++i) {
           self.completions.push(completions[i]);
           var li = document.createElement('li');
           li.innerHTML = completions[i].render();
-- 
cgit v1.2.3


From 6979cd6955ef9be7b55348c1cfc6cc2d9a3c6c76 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 04:26:12 +0100
Subject: decrease number of history items

---
 fuzzyMode.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 6e2867d2..df428cd0 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -10,7 +10,7 @@ var fuzzyMode = (function() {
           ';'    : [ 'goto',           '%s' ],
           '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         }),
-        new completion.FuzzyHistoryCompleter(1000),
+        new completion.FuzzyHistoryCompleter(500),
         new completion.FuzzyBookmarkCompleter(),
       ]);
       completer.refresh();
-- 
cgit v1.2.3


From 8f126b03e6644be45c9b046fb1a1a682f95eb085 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 13:32:16 +0100
Subject: underscore is not a word character in our context

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index 0b4c5a0a..d6a901ae 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -7,7 +7,7 @@ var completion = (function() {
     var self = {};
 
     self.matcherCacheSize = 300;
-    self.regexNonWord = /\W*/g;
+    self.regexNonWord = /[\W_]/i;
 
     // cache generated regular expressions
     self.matcherCache = {};
-- 
cgit v1.2.3


From 0bcad9357ad0a774ce2190f1e990dcdd17762c2a Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 13:36:03 +0100
Subject: improve relevancy calculation

---
 lib/completion.js | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index d6a901ae..d0c798c8 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -21,16 +21,23 @@ var completion = (function() {
     }
 
     /** Calculates a very simple similarity value between a :query and a :string. The current
-      * implementation simply returns the length of the longest prefix of :query that is found within :str.
+      * implementation simply returns the cumulated length of query parts that are also in the string.
       */
     self.calculateRelevancy = function(query, str) {
       query = self.normalize(query);
       str   = self.normalize(str);
-      for (var i = query.length; i >= 0; --i) {
-        if (str.indexOf(query.slice(0, i)) >= 0)
-          return i;
+      var sum = 0;
+      // only iterate over slices of the query starting at an offset up to 10 to save resources
+      for (var start = 0; start < 10; ++start) {
+        for (var i = query.length; i >= start; --i) {
+          if (str.indexOf(query.slice(start, i)) >= 0) {
+            sum += i - start;
+            break;
+          }
+
+        }
       }
-      return 0;
+      return sum;
     }
 
     /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
-- 
cgit v1.2.3


From 3520212b6ef4945b96fc061ecfe7c198195e1ee4 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 15:44:13 +0100
Subject: move some logic from background to content page

---
 background_page.html | 17 ++---------------
 lib/completion.js    |  2 ++
 2 files changed, 4 insertions(+), 15 deletions(-)

diff --git a/background_page.html b/background_page.html
index bca446a6..97017fad 100644
--- a/background_page.html
+++ b/background_page.html
@@ -291,8 +291,6 @@
     chrome.bookmarks.getTree(function(bookmarks) {
       var results = [];
       traverseTree(bookmarks, function(bookmark) {
-        if (typeof bookmark.url === "undefined")
-          return;
         results.push(bookmark);
       });
       port.postMessage({bookmarks:results});
@@ -302,19 +300,8 @@
   function getHistory(args, port) {
     chrome.history.search({ text: '',
                             maxResults: args.maxResults || 1000 },
-                      function(history) {
-      // sort by visit cound descending
-      history.sort(function(a, b) {
-        // visitCount may be undefined
-        var visitCountForA = a.visitCount || 0;
-        var visitCountForB = a.visitCount || 0;
-        return visitCountForB - visitCountForA;
-      });
-      var results = [];
-      for (var i = 0; i < history.length; ++i) {
-        results.push(history[i]);
-      }
-      port.postMessage({history:results});
+                          function(history) {
+      port.postMessage({history:history});
     });
   };
 
diff --git a/lib/completion.js b/lib/completion.js
index d0c798c8..1eb87d51 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -356,6 +356,8 @@ var completion = (function() {
 
       for (var i = 0; i < msg.bookmarks.length; ++i) {
         var bookmark = msg.bookmarks[i];
+        if (bookmark.url === undefined)
+          continue;
 
         var title = '';
         if (bookmark.title.length > 0)
-- 
cgit v1.2.3


From 642694bcc5850b31648bf56d8e2bd65184f377d3 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 15:53:25 +0100
Subject: fix relevancy heuristic

---
 lib/completion.js | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 1eb87d51..afdb7f55 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -21,7 +21,8 @@ var completion = (function() {
     }
 
     /** Calculates a very simple similarity value between a :query and a :string. The current
-      * implementation simply returns the cumulated length of query parts that are also in the string.
+      * implementation simply returns the cumulated length of query parts that are also found
+      * in the string, raised to the power of 3.
       */
     self.calculateRelevancy = function(query, str) {
       query = self.normalize(query);
@@ -37,7 +38,7 @@ var completion = (function() {
 
         }
       }
-      return sum;
+      return sum * sum * sum;
     }
 
     /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
@@ -201,13 +202,15 @@ var completion = (function() {
     this.readyCallback = this.fallbackReadyCallback = function(results) {
       this.completions = results;
     }
+    this.extractStringFromMatch = function(match) { return stripHtmlTags(match.str); }
   }
   AsyncFuzzyUrlCompleter.prototype = {
     // to be implemented by subclasses
     refresh: function() { },
 
     calculateRelevancy: function(query, match) {
-      return match.url.length * 10 / (fuzzyMatcher.calculateRelevancy(query, match.str)+1);
+      return match.url.length * 10 /
+        (fuzzyMatcher.calculateRelevancy(query, this.extractStringFromMatch(match)) + 1);
     },
 
     filter: function(query, callback) {
@@ -216,7 +219,7 @@ var completion = (function() {
       var handler = function(results) {
         var filtered = [];
         fuzzyMatcher.filter(query,
-                            results, function(comp) { return stripHtmlTags(comp.str) },
+                            results, self.extractStringFromMatch,
                             self.id,
                             function(match) {
           filtered.push(createHighlightingCompletion(
-- 
cgit v1.2.3


From f0409c59deb17443156d5f880081cd0d0bb9661d Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 15:59:18 +0100
Subject: add Google lucky search as command "luck "

---
 fuzzyMode.js | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index df428cd0..41fc061b 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -6,6 +6,7 @@ var fuzzyMode = (function() {
       var completer = new completion.MergingCompleter([
         new completion.SmartCompleter({
           'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
+          'luck ': [ 'Google Lucky (en)', 'http://www.google.com/search?q=%s&btnI=I%27m+Feeling+Lucky' ],
           'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
           ';'    : [ 'goto',           '%s' ],
           '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
-- 
cgit v1.2.3


From 53f8158919d8b916818c54c6a9e4bf12d28df0f0 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sat, 21 Jan 2012 16:27:42 +0100
Subject: add tab completion support

---
 background_page.html | 18 +++++++++++++++++-
 fuzzyMode.js         |  1 +
 lib/completion.js    | 45 ++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 62 insertions(+), 2 deletions(-)

diff --git a/background_page.html b/background_page.html
index 97017fad..0f86e3ce 100644
--- a/background_page.html
+++ b/background_page.html
@@ -29,6 +29,7 @@
     getBookmarks:         getBookmarks,
     getAllBookmarks:      getAllBookmarks,
     getHistory:           getHistory,
+    getTabsInCurrentWindow: getTabsInCurrentWindow,
   };
 
   var sendRequestHandlers = {
@@ -43,7 +44,8 @@
     updateScrollPosition: handleUpdateScrollPosition,
     copyToClipboard: copyToClipboard,
     isEnabledForUrl: isEnabledForUrl,
-    saveHelpDialogSettings: saveHelpDialogSettings
+    saveHelpDialogSettings: saveHelpDialogSettings,
+    selectSpecificTab: selectSpecificTab,
   };
 
   // Event handlers
@@ -259,6 +261,14 @@
     Clipboard.copy(request.data);
   }
 
+  /**
+    * Selects the tab with the ID specified in request.id
+    */
+  function selectSpecificTab(request) {
+    console.log("selectSpecificTab");
+    chrome.tabs.update(request.id, { selected: true });
+  }
+
   /*
    * Used by the content scripts to get settings from the local storage.
    */
@@ -305,6 +315,12 @@
     });
   };
 
+  function getTabsInCurrentWindow(args, port) {
+    chrome.tabs.getAllInWindow(null, function(tabs) {
+      port.postMessage({tabs:tabs});
+    });
+  };
+
   /*
    * Used by everyone to get settings from local storage.
    */
diff --git a/fuzzyMode.js b/fuzzyMode.js
index 41fc061b..32f54eb9 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -13,6 +13,7 @@ var fuzzyMode = (function() {
         }),
         new completion.FuzzyHistoryCompleter(500),
         new completion.FuzzyBookmarkCompleter(),
+        new completion.FuzzyTabCompleter(),
       ]);
       completer.refresh();
       fuzzyBox = new FuzzyBox(completer, 10);
diff --git a/lib/completion.js b/lib/completion.js
index afdb7f55..f78a9e39 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -213,6 +213,10 @@ var completion = (function() {
         (fuzzyMatcher.calculateRelevancy(query, this.extractStringFromMatch(match)) + 1);
     },
 
+    createAction: function(match) {
+      return createActionOpenUrl(match.url);
+    },
+
     filter: function(query, callback) {
       var self = this;
 
@@ -224,7 +228,7 @@ var completion = (function() {
                             function(match) {
           filtered.push(createHighlightingCompletion(
                 query, match.str,
-                createActionOpenUrl(match.url),
+                self.createAction(match),
                 self.calculateRelevancy(query, match)));
         });
         callback(filtered);
@@ -377,6 +381,44 @@ var completion = (function() {
     port.postMessage();
   }
 
+  /** A fuzzy tab completer */
+  var FuzzyTabCompleter = function() {
+    AsyncFuzzyUrlCompleter.call(this);
+  }
+  FuzzyTabCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  FuzzyTabCompleter.prototype.createAction = function(match) {
+    var open = function() {
+      chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: match.tab.id });
+    }
+    return [ open, open ];
+  }
+  FuzzyTabCompleter.prototype.refresh = function() {
+    this.completions = null; // reset completions
+
+    var port = chrome.extension.connect({ name: 'getTabsInCurrentWindow' }) ;
+    var self = this;
+    port.onMessage.addListener(function(msg) {
+      var results = [];
+
+      for (var i = 0; i < msg.tabs.length; ++i) {
+        var tab = msg.tabs[i];
+
+        var title = '';
+        if (tab.title.length > 0)
+          title = ' <span class="title">' + tab.title + '</span>';
+
+        results.push({
+          str: '<em>tab</em> ' + tab.url + title,
+          url: tab.url,
+          tab: tab,
+        });
+      }
+      port = null;
+      self.readyCallback(results);
+    });
+    port.postMessage();
+  }
+
   /** A meta-completer that delegates queries and merges and sorts the results of a collection of other
    * completer instances. */
   var MergingCompleter = function(sources) {
@@ -412,6 +454,7 @@ var completion = (function() {
   return {
     FuzzyHistoryCompleter: FuzzyHistoryCompleter,
     FuzzyBookmarkCompleter: FuzzyBookmarkCompleter,
+    FuzzyTabCompleter: FuzzyTabCompleter,
     SmartCompleter: SmartCompleter,
     MergingCompleter: MergingCompleter,
   };
-- 
cgit v1.2.3


From 76b26a8a25522300b9e6e463e75397693fa2bb53 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sun, 22 Jan 2012 13:46:17 +0100
Subject: really get more history items

---
 background_page.html | 8 +++++---
 fuzzyMode.js         | 2 +-
 2 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/background_page.html b/background_page.html
index 0f86e3ce..c065333d 100644
--- a/background_page.html
+++ b/background_page.html
@@ -308,9 +308,11 @@
   };
 
   function getHistory(args, port) {
-    chrome.history.search({ text: '',
-                            maxResults: args.maxResults || 1000 },
-                          function(history) {
+    chrome.history.search({
+        text: '',
+        maxResults: args.maxResults || 1000,
+        startTime: 0,
+    }, function(history) {
       port.postMessage({history:history});
     });
   };
diff --git a/fuzzyMode.js b/fuzzyMode.js
index 32f54eb9..90ba0aa4 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -11,7 +11,7 @@ var fuzzyMode = (function() {
           ';'    : [ 'goto',           '%s' ],
           '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         }),
-        new completion.FuzzyHistoryCompleter(500),
+        new completion.FuzzyHistoryCompleter(2000),
         new completion.FuzzyBookmarkCompleter(),
         new completion.FuzzyTabCompleter(),
       ]);
-- 
cgit v1.2.3


From 516101bf1350cd77cd71423a2cbdf639f33dfd85 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sun, 22 Jan 2012 13:48:26 +0100
Subject: remove debug statement

---
 background_page.html | 1 -
 1 file changed, 1 deletion(-)

diff --git a/background_page.html b/background_page.html
index c065333d..641fea1f 100644
--- a/background_page.html
+++ b/background_page.html
@@ -265,7 +265,6 @@
     * Selects the tab with the ID specified in request.id
     */
   function selectSpecificTab(request) {
-    console.log("selectSpecificTab");
     chrome.tabs.update(request.id, { selected: true });
   }
 
-- 
cgit v1.2.3


From fc545ea6da22ec7ca2d0a7a2cfa16135fa219a7c Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sun, 22 Jan 2012 14:23:56 +0100
Subject: improve string ranking

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index f78a9e39..446b9cab 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -29,7 +29,7 @@ var completion = (function() {
       str   = self.normalize(str);
       var sum = 0;
       // only iterate over slices of the query starting at an offset up to 10 to save resources
-      for (var start = 0; start < 10; ++start) {
+      for (var start = 0; start < 20; ++start) {
         for (var i = query.length; i >= start; --i) {
           if (str.indexOf(query.slice(start, i)) >= 0) {
             sum += i - start;
-- 
cgit v1.2.3


From 469147824fd2fb8d83d16a28f3d3c613e69b4573 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sun, 22 Jan 2012 16:23:26 +0100
Subject: prefer marking continguous characters

---
 lib/completion.js | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 446b9cab..67d8b219 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -20,6 +20,38 @@ var completion = (function() {
       return query.replace(self.regexNonWord, '').toLowerCase();
     }
 
+    /** Returns the non-matching and matching string parts, in alternating order (starting with a
+     * non-matching part) or null, if the string doesn't match the query.
+     *
+     * Sample: match("codecodec","code.google.com/codec") would yield ["", "code", ".google.com/", "codec"]
+     *
+     * Note that this function matches the longest possible parts of a string and is therefore not very
+     * efficient. _Don't use this to check if a string matches a query_. Use `getMatcher(query).test(str)`
+     * instead.
+     */
+    self.match = function(query, str) {
+      query = self.normalize(query);
+      if (query.length == 0)
+        return str.length ? [str] : [];
+
+      for (var i = query.length; i >= 1; --i) {
+        var part = query.slice(0, i);
+        var partOffset = str.toLowerCase().indexOf(part);
+        if (partOffset < 0)
+          continue;
+
+        // we use recursive backtracking here, this is why it's slow.
+        rest = self.match(query.slice(i), str.slice(partOffset + i));
+        if (!rest) continue;
+
+        return [
+          str.slice(0, partOffset),
+          part,
+        ].concat(rest);
+      }
+      return null;
+    }
+
     /** Calculates a very simple similarity value between a :query and a :string. The current
       * implementation simply returns the cumulated length of query parts that are also found
       * in the string, raised to the power of 3.
@@ -155,30 +187,35 @@ var completion = (function() {
         // tags and reinsert them after the matching process
         var htmlTags = {};
         str = stripHtmlTags(str, htmlTags);
-        var match = fuzzyMatcher.getMatcher(query).exec(str);
+        var groups = fuzzyMatcher.match(query, str);
         var html = '';
-        var i = 0;
+        var htmlOffset = 0;
 
         // this helper function adds the HTML generated _for one single character_ to the HTML output
         // and reinserts HTML tags stripped before, if they were at this position
         function addToHtml(str) {
-          if (i in htmlTags)
-            html += htmlTags[i];
+          if (htmlOffset in htmlTags)
+            html += htmlTags[htmlOffset];
           html += str;
-          ++i;
+          ++htmlOffset;
+        }
+
+        function addCharsWithDecoration(str, before, after) {
+          before = before || '';
+          after = after || '';
+          for (var i = 0; i < str.length; ++i)
+            addToHtml(before + str[i] + after);
         }
 
         // iterate over the match groups. They are non-matched and matched string parts, in alternating order
-        for (var m = 1; m < match.length; ++m) {
-          if (m % 2 == 1)
+        for (var i = 0; i < groups.length; ++i) {
+          if (i % 2 == 0)
             // we have a non-matched part, it could have several characters. We need to insert them character
             // by character, so that addToHtml can keep track of the position in the original string
-            for (var j = 0; j < match[m].length; ++j)
-              addToHtml(match[m][j]);
+            addCharsWithDecoration(groups[i]);
           else
-            // we have a matched part, which consists of exactly one character. In addition to the character
-            // itself, we add some decorating HTML.
-            addToHtml('<span class="fuzzyMatch">' + match[m] + '</span>');
+            // we have a matched part. In addition to the characters themselves, we add some decorating HTML.
+            addCharsWithDecoration(groups[i], '<span class="fuzzyMatch">', '</span>');
         };
 
         // call it another time so that a tag at the very last position is reinserted
-- 
cgit v1.2.3


From 2c5b91634f7748e70730265c0fe7bb54d91fd213 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Sun, 22 Jan 2012 22:10:31 +0100
Subject: use background page to open URLs

---
 lib/completion.js | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 67d8b219..d0e9e32a 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -170,10 +170,20 @@ var completion = (function() {
 
   /** Creates an action that opens :url in the current tab by default or in a new tab as an alternative. */
   function createActionOpenUrl(url) {
-    return [
-      function() { window.location = url; },
-      function() { window.open(url); },
-    ]
+    var open = function(newTab, selected) {
+      return function() {
+        chrome.extension.sendRequest({
+          handler:  newTab ? "openUrlInNewTab" : "openUrlInCurrentTab",
+          url:      url,
+          selected: selected
+        });
+      }
+    }
+
+    if (url.indexOf("javascript:") == 0)
+      return [ open(false), open(false), open(false) ];
+    else
+      return [ open(false), open(true, true), open(true, false) ];
   }
 
   /** Creates a completion that renders by marking fuzzy-matched parts. */
-- 
cgit v1.2.3


From 9c3ea936687fa08161fa9f57d90233cb3796ff0d Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 12:41:48 +0100
Subject: fix bug in query normalization

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index d0e9e32a..126790ff 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -7,7 +7,7 @@ var completion = (function() {
     var self = {};
 
     self.matcherCacheSize = 300;
-    self.regexNonWord = /[\W_]/i;
+    self.regexNonWord = /[\W_]/ig;
 
     // cache generated regular expressions
     self.matcherCache = {};
-- 
cgit v1.2.3


From 9890e1700f1348ac6284f185e296b8e4402ffa51 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 12:42:04 +0100
Subject: restructure fuzzy mode flow

---
 commands.js  | 10 ++++-----
 fuzzyMode.js | 67 ++++++++++++++++++++++++++++++++++++++++--------------------
 2 files changed, 50 insertions(+), 27 deletions(-)

diff --git a/commands.js b/commands.js
index 1c19e26a..2cfd5cfa 100644
--- a/commands.js
+++ b/commands.js
@@ -144,8 +144,8 @@ function clearKeyMappingsAndSetDefaults() {
     "b": "activateBookmarkFindMode",
     "B": "activateBookmarkFindModeToOpenInNewTab",
 
-    "o": "fuzzyMode.activate",
-    "O": "fuzzyMode.activateNewTab",
+    "o": "fuzzyMode.activateAll",
+    "O": "fuzzyMode.activateAllNewTab",
 
     "gf": "nextFrame",
   };
@@ -214,8 +214,8 @@ var commandDescriptions = {
   activateBookmarkFindMode: ["Open a bookmark in the current tab"],
   activateBookmarkFindModeToOpenInNewTab: ["Open a bookmark in a new tab"],
 
-  'fuzzyMode.activate': ["Open URL, bookmark, history entry or a custom search (fuzzy)"],
-  'fuzzyMode.activateNewTab': ["Open URL, bookmark, history entry or a custom search (fuzzy, new tab)"],
+  'fuzzyMode.activateAll': ["Open URL, bookmark, history entry or a custom search (fuzzy)"],
+  'fuzzyMode.activateAllNewTab': ["Open URL, bookmark, history entry or a custom search (fuzzy, new tab)"],
 
   nextFrame: ["Cycle forward to the next frame on the page", { background: true, passCountToFunction: true }]
 };
@@ -236,7 +236,7 @@ var commandGroups = {
      "enterInsertMode", "focusInput",
      "linkHints.activateMode", "linkHints.activateModeToOpenInNewTab", "linkHints.activateModeWithQueue",
      "activateBookmarkFindMode", "activateBookmarkFindModeToOpenInNewTab",
-     "fuzzyMode.activate", "fuzzyMode.activateNewTab",
+     "fuzzyMode.activateAll", "fuzzyMode.activateAllNewTab",
      "goPrevious", "goNext", "nextFrame"],
   findCommands: ["enterFindMode", "performFind", "performBackwardsFind"],
   historyNavigation:
diff --git a/fuzzyMode.js b/fuzzyMode.js
index 90ba0aa4..b332d084 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -1,35 +1,58 @@
 var fuzzyMode = (function() {
+  var fuzzyBox = null;  // the dialog instance for this window
+  var completers = {};  // completer cache
+
+  function createCompleter(name) {
+    if (name === 'smart')
+      return new completion.SmartCompleter({
+        'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
+        'luck ': [ 'Google Lucky (en)', 'http://www.google.com/search?q=%s&btnI=I%27m+Feeling+Lucky' ],
+        'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
+        ';'    : [ 'goto',           '%s' ],
+        '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
+        });
+    else if (name === 'history')
+      return new completion.FuzzyHistoryCompleter(2000);
+    else if (name === 'bookmarks')
+      return new completion.FuzzyBookmarkCompleter();
+    else if (name === 'tabs')
+      return new completion.FuzzyTabCompleter();
+    else if (name === 'all')
+      return new completion.MergingCompleter([
+        getCompleter('smart'),
+        getCompleter('history'),
+        getCompleter('tabs'),
+        ]);
+  }
+  function getCompleter(name) {
+    if (!(name in completers))
+      completers[name] = createCompleter(name);
+    return completers[name];
+  }
+
   /** Trigger the fuzzy mode dialog */
-  var fuzzyBox = null;
-  function start(newTab) {
-    if (!fuzzyBox) {
-      var completer = new completion.MergingCompleter([
-        new completion.SmartCompleter({
-          'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
-          'luck ': [ 'Google Lucky (en)', 'http://www.google.com/search?q=%s&btnI=I%27m+Feeling+Lucky' ],
-          'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
-          ';'    : [ 'goto',           '%s' ],
-          '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
-        }),
-        new completion.FuzzyHistoryCompleter(2000),
-        new completion.FuzzyBookmarkCompleter(),
-        new completion.FuzzyTabCompleter(),
-      ]);
-      completer.refresh();
-      fuzzyBox = new FuzzyBox(completer, 10);
-    }
+  function start(name, newTab) {
+    var completer = getCompleter(name);
+    if (!fuzzyBox)
+      fuzzyBox = new FuzzyBox(10);
+    completer.refresh();
+    fuzzyBox.setCompleter(completer);
     fuzzyBox.show(newTab);
   }
 
   /** User interface for fuzzy completion */
-  var FuzzyBox = function(completer, maxResults) {
+  var FuzzyBox = function(maxResults) {
     this.prompt = '> ';
     this.maxResults = maxResults || 10;
-    this.completer = completer;
     this.initDom();
     this.reset();
   }
   FuzzyBox.prototype = {
+    setCompleter: function(completer) {
+      this.completer = completer;
+      this.reset();
+    },
+
     show: function(reverseAction) {
       this.reverseAction = reverseAction;
       this.box.style.display = 'block';
@@ -168,8 +191,8 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activate:       function() { start(false); },
-    activateNewTab: function() { start(true);  },
+    activateAll:       function() { start('all', false); },
+    activateAllNewTab: function() { start('all', true);  },
   }
 
 })();
-- 
cgit v1.2.3


From 9bab5a39e49c348c10941882395e68c0351a8a39 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 12:57:32 +0100
Subject: add special command for tab completion

---
 commands.js  | 5 ++++-
 fuzzyMode.js | 9 +++++----
 2 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/commands.js b/commands.js
index 2cfd5cfa..727bf3c7 100644
--- a/commands.js
+++ b/commands.js
@@ -147,6 +147,8 @@ function clearKeyMappingsAndSetDefaults() {
     "o": "fuzzyMode.activateAll",
     "O": "fuzzyMode.activateAllNewTab",
 
+    "T": "fuzzyMode.activateTabs",
+
     "gf": "nextFrame",
   };
 
@@ -216,6 +218,7 @@ var commandDescriptions = {
 
   'fuzzyMode.activateAll': ["Open URL, bookmark, history entry or a custom search (fuzzy)"],
   'fuzzyMode.activateAllNewTab': ["Open URL, bookmark, history entry or a custom search (fuzzy, new tab)"],
+  'fuzzyMode.activateTabs': ["Go to a tab in this window (fuzzy)"],
 
   nextFrame: ["Cycle forward to the next frame on the page", { background: true, passCountToFunction: true }]
 };
@@ -236,7 +239,7 @@ var commandGroups = {
      "enterInsertMode", "focusInput",
      "linkHints.activateMode", "linkHints.activateModeToOpenInNewTab", "linkHints.activateModeWithQueue",
      "activateBookmarkFindMode", "activateBookmarkFindModeToOpenInNewTab",
-     "fuzzyMode.activateAll", "fuzzyMode.activateAllNewTab",
+     "fuzzyMode.activateAll", "fuzzyMode.activateAllNewTab", "fuzzyMode.activateTabs",
      "goPrevious", "goNext", "nextFrame"],
   findCommands: ["enterFindMode", "performFind", "performBackwardsFind"],
   historyNavigation:
diff --git a/fuzzyMode.js b/fuzzyMode.js
index b332d084..8f5ccef0 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -31,13 +31,13 @@ var fuzzyMode = (function() {
   }
 
   /** Trigger the fuzzy mode dialog */
-  function start(name, newTab) {
+  function start(name, reverseAction) {
     var completer = getCompleter(name);
     if (!fuzzyBox)
       fuzzyBox = new FuzzyBox(10);
     completer.refresh();
     fuzzyBox.setCompleter(completer);
-    fuzzyBox.show(newTab);
+    fuzzyBox.show(reverseAction);
   }
 
   /** User interface for fuzzy completion */
@@ -191,8 +191,9 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activateAll:       function() { start('all', false); },
-    activateAllNewTab: function() { start('all', true);  },
+    activateAll:       function() { start('all',  false); },
+    activateAllNewTab: function() { start('all',  true);  },
+    activateTabs:      function() { start('tabs', false); },
   }
 
 })();
-- 
cgit v1.2.3


From aa5b39f3e211169d43ec7c3ce5bdd39b49a54f44 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 12:57:51 +0100
Subject: fix search URL building

---
 lib/utils.js | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/utils.js b/lib/utils.js
index 2b580786..a0ca9715 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -100,7 +100,8 @@ var utils = {
    * Creates a search URL from the given :query.
    */
   createSearchUrl: function(query) {
-    return "http://www.google.com/search?q=" + query;
+    // we need to escape explictely to encode characters like "+" correctly
+    return "http://www.google.com/search?q=" + encodeURIComponent(query);
   },
 
   /**
-- 
cgit v1.2.3


From 6be4f6164b468cdc0657defe3825fde745ef7116 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 13:17:09 +0100
Subject: make CSS more robust

---
 vimium.css | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/vimium.css b/vimium.css
index 5d0f69ad..53bc50d8 100644
--- a/vimium.css
+++ b/vimium.css
@@ -326,11 +326,15 @@ body.vimiumFindMode ::selection {
 
 #fuzzybox li .fuzzyMatch {
   color: red !important;
+  font-size: inherit !important;
+  font-family: inherit !important;
 }
 
 #fuzzybox li em, #fuzzybox li .title {
   color: #444 !important;
   font-weight: normal !important;
+  font-size: inherit !important;
+  font-family: inherit !important;
 }
 #fuzzybox li em {
   font-style: italic !important;
@@ -346,6 +350,7 @@ body.vimiumFindMode ::selection {
   color: #ccc !important;
   border-radius: 4px !important;
   font-weight: normal !important;
+  font-family: inherit !important;
 }
 #fuzzybox li.selected em, #fuzzybox li.selected .title {
   color: #666 !important;
@@ -355,8 +360,12 @@ body.vimiumFindMode ::selection {
   font-size: 28px !important;
   padding: 0 !important;
   margin: 0 !important;
+  font-size: inherit !important;
+  font-family: inherit !important;
 }
 
 #fuzzybox .input .prompt {
   color: orange !important;
+  font-size: inherit !important;
+  font-family: inherit !important;
 }
-- 
cgit v1.2.3


From 8e20171da3dedfbd737d82c24147011f61690a79 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 13:28:54 +0100
Subject: fix ranking algorithm

---
 lib/completion.js | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 126790ff..5950a1ca 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -61,13 +61,12 @@ var completion = (function() {
       str   = self.normalize(str);
       var sum = 0;
       // only iterate over slices of the query starting at an offset up to 10 to save resources
-      for (var start = 0; start < 20; ++start) {
+      for (var start = 0; start < 20 && start < query.length; ++start) {
         for (var i = query.length; i >= start; --i) {
           if (str.indexOf(query.slice(start, i)) >= 0) {
-            sum += i - start;
+            sum += (i - start) * (i - start);
             break;
           }
-
         }
       }
       return sum * sum * sum;
@@ -256,7 +255,7 @@ var completion = (function() {
     refresh: function() { },
 
     calculateRelevancy: function(query, match) {
-      return match.url.length * 10 /
+      return match.url.length /
         (fuzzyMatcher.calculateRelevancy(query, this.extractStringFromMatch(match)) + 1);
     },
 
-- 
cgit v1.2.3


From de0a3607fd0a1e788d314f24894ba72315a64771 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 13:29:12 +0100
Subject: sort results in tab completion mode

---
 fuzzyMode.js | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8f5ccef0..a91fab37 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -17,6 +17,8 @@ var fuzzyMode = (function() {
       return new completion.FuzzyBookmarkCompleter();
     else if (name === 'tabs')
       return new completion.FuzzyTabCompleter();
+    else if (name === 'tabsSorted')
+      return new completion.MergingCompleter([getCompleter('tabs')]);
     else if (name === 'all')
       return new completion.MergingCompleter([
         getCompleter('smart'),
@@ -191,9 +193,9 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activateAll:       function() { start('all',  false); },
-    activateAllNewTab: function() { start('all',  true);  },
-    activateTabs:      function() { start('tabs', false); },
+    activateAll:       function() { start('all',        false); },
+    activateAllNewTab: function() { start('all',        true);  },
+    activateTabs:      function() { start('tabsSorted', false); },
   }
 
 })();
-- 
cgit v1.2.3


From 59b096f2c4d9f5406cfa10f71b64887ef1e9fa49 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 15:08:28 +0100
Subject: fall back to regex matching for long queries

---
 lib/completion.js | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 5950a1ca..077dcc80 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -26,13 +26,20 @@ var completion = (function() {
      * Sample: match("codecodec","code.google.com/codec") would yield ["", "code", ".google.com/", "codec"]
      *
      * Note that this function matches the longest possible parts of a string and is therefore not very
-     * efficient. _Don't use this to check if a string matches a query_. Use `getMatcher(query).test(str)`
-     * instead.
+     * efficient. There it falls back to a more performant, but less accurate regex matching if the
+     * normalized query is longer than 10 characters.
+     *
+     * _Don't use this to check if a string matches a query_. Use `getMatcher(query).test(str)` instead.
      */
     self.match = function(query, str) {
       query = self.normalize(query);
       if (query.length == 0)
         return str.length ? [str] : [];
+      if (query.length > 10) {
+        // for long query strings, the method is much too inefficient, so fall
+        // back to the more inaccurate regex matching
+        return self.getMatcher(query).exec(str).slice(1);
+      }
 
       for (var i = query.length; i >= 1; --i) {
         var part = query.slice(0, i);
-- 
cgit v1.2.3


From 8179e6da52f516b528ba000f1a038a59f86d37a6 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 16:35:31 +0100
Subject: raise regex threshold to query length 15

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index 077dcc80..697ee831 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -35,7 +35,7 @@ var completion = (function() {
       query = self.normalize(query);
       if (query.length == 0)
         return str.length ? [str] : [];
-      if (query.length > 10) {
+      if (query.length > 15) {
         // for long query strings, the method is much too inefficient, so fall
         // back to the more inaccurate regex matching
         return self.getMatcher(query).exec(str).slice(1);
-- 
cgit v1.2.3


From 958dd003ea7f3aaefc7c785bbb353b1c26641bc1 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 21:53:10 +0100
Subject: fix bad English

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index 697ee831..1c4d60c0 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -37,7 +37,7 @@ var completion = (function() {
         return str.length ? [str] : [];
       if (query.length > 15) {
         // for long query strings, the method is much too inefficient, so fall
-        // back to the more inaccurate regex matching
+        // back to the less accurate regex matching
         return self.getMatcher(query).exec(str).slice(1);
       }
 
-- 
cgit v1.2.3


From 6bc1d44939c9b4557ef8648a6e645e73caaa0623 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 22:29:13 +0100
Subject: improve perfmance by caching history results in the background page.

Also decrease the number of included results slightly.
---
 background_page.html | 33 ++++++++++++++++++++++++++++++---
 fuzzyMode.js         |  2 +-
 2 files changed, 31 insertions(+), 4 deletions(-)

diff --git a/background_page.html b/background_page.html
index 641fea1f..99c7d430 100644
--- a/background_page.html
+++ b/background_page.html
@@ -75,6 +75,8 @@
     if (portHandlers[port.name])
       port.onMessage.addListener(portHandlers[port.name]);
 
+    // prefetch history
+    useHistory(function() {});
   });
 
   chrome.extension.onRequest.addListener(function (request, sender, sendResponse) {
@@ -306,13 +308,38 @@
     });
   };
 
-  function getHistory(args, port) {
+  var cachedHistory = null;
+  function useHistory(callback) {
+    if (cachedHistory !== null) {
+      callback(cachedHistory);
+      return;
+    }
+
     chrome.history.search({
         text: '',
-        maxResults: args.maxResults || 1000,
+        maxResults: 20000,
         startTime: 0,
     }, function(history) {
-      port.postMessage({history:history});
+      // sorting in asceding order, so we can push new items to the end later
+      history.sort(function(a, b) {
+        // visitCount may be undefined
+        return (a.visitCount || 0) - (b.visitCount || 0);
+      });
+      cachedHistory = history;
+      callback(cachedHistory);
+    });
+  }
+
+  chrome.history.onVisited.addListener(function(item) {
+    if (cachedHistory === null) return;
+    cachedHistory.push(item);
+  });
+
+  function getHistory(args, port) {
+    useHistory(function(history) {
+      port.postMessage({
+        history: history.slice(history.length - args.maxResults)
+      });
     });
   };
 
diff --git a/fuzzyMode.js b/fuzzyMode.js
index a91fab37..a98e3f21 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -12,7 +12,7 @@ var fuzzyMode = (function() {
         '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         });
     else if (name === 'history')
-      return new completion.FuzzyHistoryCompleter(2000);
+      return new completion.FuzzyHistoryCompleter(1500);
     else if (name === 'bookmarks')
       return new completion.FuzzyBookmarkCompleter();
     else if (name === 'tabs')
-- 
cgit v1.2.3


From 14cb3e4f8e552c082cae799f8dca511c6c267891 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Mon, 23 Jan 2012 23:11:45 +0100
Subject: minor optimizations and code cleanup

---
 lib/completion.js | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 1c4d60c0..04899ca8 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -6,6 +6,7 @@ var completion = (function() {
   var fuzzyMatcher = (function() {
     var self = {};
 
+    self.timeToClean = 0;
     self.matcherCacheSize = 300;
     self.regexNonWord = /[\W_]/ig;
 
@@ -121,6 +122,7 @@ var completion = (function() {
 
       // find the most specific list of sources in the cache
       var maxSpecificity = 0;
+      var specificity;
       for (key in self.filterCache[id]) {
         if (!self.filterCache[id].hasOwnProperty(key))
           continue;
@@ -132,24 +134,23 @@ var completion = (function() {
         }
 
         // is this cache entry the most specific so far?
-        var specificity = self.filterCache[id][key].length;
+        specificity = self.filterCache[id][key].length;
         if (query.indexOf(key) == 0 && specificity > maxSpecificity) {
           source = self.filterCache[id][key];
           maxSpecificity = specificity;
         }
       }
 
-      // clean up
-      self.cleanMatcherCache();
+      // clean up every few calls
+      if (++self.timeToClean > 20) {
+        self.timeToClean = 0;
+        self.cleanMatcherCache();
+      }
 
       var matcher = self.getMatcher(query);
-      for (var i = 0; i < source.length; ++i) {
-        if (!matcher.test(getValue(source[i])))
-          continue;
-        filtered.push(source[i]);
-        callback(source[i]);
-      }
+      var filtered = source.filter(function(x) { return matcher.test(getValue(x)) });
       self.filterCache[id][query] = filtered;
+      return filtered;
     }
 
     return self;
@@ -274,17 +275,13 @@ var completion = (function() {
       var self = this;
 
       var handler = function(results) {
-        var filtered = [];
-        fuzzyMatcher.filter(query,
-                            results, self.extractStringFromMatch,
-                            self.id,
-                            function(match) {
-          filtered.push(createHighlightingCompletion(
+        var filtered = fuzzyMatcher.filter(query, results, self.extractStringFromMatch, self.id);
+        callback(filtered.map(function(match) {
+          return createHighlightingCompletion(
                 query, match.str,
                 self.createAction(match),
-                self.calculateRelevancy(query, match)));
-        });
-        callback(filtered);
+                self.calculateRelevancy(query, match));
+        }));
       }
 
       // are the results ready?
-- 
cgit v1.2.3


From 2eae98f3b4b6cccaa49f91b282854c39145f12a4 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 00:08:04 +0100
Subject: improve comments and fix some naming style inconsistencies

---
 background_page.html |  2 +-
 lib/completion.js    | 38 ++++++++++++++++----------------------
 2 files changed, 17 insertions(+), 23 deletions(-)

diff --git a/background_page.html b/background_page.html
index 99c7d430..f220d76c 100644
--- a/background_page.html
+++ b/background_page.html
@@ -320,7 +320,7 @@
         maxResults: 20000,
         startTime: 0,
     }, function(history) {
-      // sorting in asceding order, so we can push new items to the end later
+      // sorting in ascending order, so we can push new items to the end later
       history.sort(function(a, b) {
         // visitCount may be undefined
         return (a.visitCount || 0) - (b.visitCount || 0);
diff --git a/lib/completion.js b/lib/completion.js
index 04899ca8..f06c6708 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -16,7 +16,7 @@ var completion = (function() {
     self.filterCache = {};
 
     /** Normalizes the string specified in :query. Strips any non-word characters and converts
-      * to lower case. */
+     * to lower case. */
     self.normalize = function(query) {
       return query.replace(self.regexNonWord, '').toLowerCase();
     }
@@ -61,9 +61,9 @@ var completion = (function() {
     }
 
     /** Calculates a very simple similarity value between a :query and a :string. The current
-      * implementation simply returns the cumulated length of query parts that are also found
-      * in the string, raised to the power of 3.
-      */
+     * implementation simply returns the cumulated length of query parts that are also found
+     * in the string, raised to the power of 3.
+     */
     self.calculateRelevancy = function(query, str) {
       query = self.normalize(query);
       str   = self.normalize(str);
@@ -89,8 +89,8 @@ var completion = (function() {
     }
 
     /** Returns a regex that matches a string using a fuzzy :query. Example: The :query "abc" would result
-      * in a regex like /^([^a])*(a)([^b])*(b)([^c])*(c)(.*)$/
-      */
+     * in a regex like /^([^a])*(a)([^b])*(b)([^c])*(c)(.*)$/
+     */
     self.getMatcher = function(query) {
       query = self.normalize(query);
       if (!(query in self.matcherCache)) {
@@ -103,24 +103,18 @@ var completion = (function() {
       return self.matcherCache[query];
     }
 
-    /** Clears the filter cache with the given ID. */
-    self.clearFilterCache = function(id) {
-      if (id in self.filterCache)
-        delete self.filterCache[id];
-    }
-
-    /** Filters a list :ary using fuzzy matching against an input string :query. If a query with a less
-      * specific query was issued before (e.g. if the user added a letter to the query), the cached results
-      * of the last filtering are used as a starting point, instead of :ary.
-      */
-    self.filter = function(query, ary, getValue, id, callback) {
+    /** Filters a collection :source using fuzzy matching against an input string :query. If a query with
+     * a less specific query was issued before (e.g. if the user added a letter to the query), the cached
+     * results of the last filtering are used as a starting point, instead of :source.
+     */
+    self.filter = function(query, source, getValue, id) {
       var filtered = [];
       var source = ary;
 
       if (!(id in self.filterCache))
         self.filterCache[id] = {};
 
-      // find the most specific list of sources in the cache
+      // find the most specific list of results in the cache
       var maxSpecificity = 0;
       var specificity;
       for (key in self.filterCache[id]) {
@@ -141,7 +135,7 @@ var completion = (function() {
         }
       }
 
-      // clean up every few calls
+      // don't clean up the cache every iteration
       if (++self.timeToClean > 20) {
         self.timeToClean = 0;
         self.cleanMatcherCache();
@@ -156,7 +150,7 @@ var completion = (function() {
     return self;
   })();
 
-  /** Strips HTML tags using a naive regex replacement. Optinally, saves the stripped HTML tags in a
+  /** Strips HTML tags using a naive regex replacement. Optionally, saves the stripped HTML tags in a
    * dictionary indexed by the position where the tag should be reinserted. */
   function stripHtmlTags(str, positions) {
     var result = str.replace(/<[^>]*>/g, '');
@@ -366,9 +360,9 @@ var completion = (function() {
   }
 
   /** A fuzzy history completer */
-  var FuzzyHistoryCompleter = function(maxEntries) {
+  var FuzzyHistoryCompleter = function(maxResults) {
     AsyncFuzzyUrlCompleter.call(this);
-    this.maxEntries = maxEntries || 1000;
+    this.maxResults = maxResults || 1000;
   }
   FuzzyHistoryCompleter.prototype = new AsyncFuzzyUrlCompleter;
   FuzzyHistoryCompleter.prototype.refresh = function() {
-- 
cgit v1.2.3


From a9ea93a8fb706b2d8efc847ede2b937440c66c18 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 00:08:40 +0100
Subject: DRY up code

---
 lib/completion.js | 134 +++++++++++++++++++++++-------------------------------
 1 file changed, 58 insertions(+), 76 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index f06c6708..338ccbbb 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -109,7 +109,6 @@ var completion = (function() {
      */
     self.filter = function(query, source, getValue, id) {
       var filtered = [];
-      var source = ary;
 
       if (!(id in self.filterCache))
         self.filterCache[id] = {};
@@ -265,6 +264,22 @@ var completion = (function() {
       return createActionOpenUrl(match.url);
     },
 
+    /** Convenience function to remove shared code in the completers. Clear the completion cache, sends
+     * a message to an extension port and pipes the returned message through a callback before storing it into
+     * the instance's completion cache.
+     */
+    fetchFromPort: function(name, query, callback) {
+      this.completions = null; // reset completions
+
+      // asynchronously fetch from a port
+      var port = chrome.extension.connect({ name: name }) ;
+      var self = this;
+      port.onMessage.addListener(function(msg) {
+        self.readyCallback(callback(msg));
+      });
+      port.postMessage(query);
+    },
+
     filter: function(query, callback) {
       var self = this;
 
@@ -336,6 +351,7 @@ var completion = (function() {
 
       // trim query
       query = query.replace(/^\s+|\s+$/g, '');
+      // TODO fix HTML injection
       if (utils.isUrl(query)) {
         url = utils.createFullUrl(query);
         str = '<em>goto</em> ' + query;
@@ -359,6 +375,28 @@ var completion = (function() {
     };
   }
 
+  // TODO fix HTML injection
+  function createUrlSuggestion(type, url, title) {
+    title = title.length > 0 ? ' <span class="title">' + title + '</span>' : '';
+    return { str: '<em>' + type + '</em> ' + url + title,
+             url: url };
+  }
+
+  /** Convenience function to remove shared code in the completers. Clear the completion cache, sends
+    * a message to an extension port and pipes the returned message through a callback before storing it into
+    * the instance's completion cache.
+    */
+  function fetchFromPort(self, name, query, callback) {
+    self.completions = null; // reset completions
+
+    // asynchronously fetch from a port
+    var port = chrome.extension.connect({ name: name }) ;
+    port.onMessage.addListener(function(msg) {
+      self.readyCallback(callback(msg));
+    });
+    port.postMessage(query);
+  };
+
   /** A fuzzy history completer */
   var FuzzyHistoryCompleter = function(maxResults) {
     AsyncFuzzyUrlCompleter.call(this);
@@ -366,30 +404,11 @@ var completion = (function() {
   }
   FuzzyHistoryCompleter.prototype = new AsyncFuzzyUrlCompleter;
   FuzzyHistoryCompleter.prototype.refresh = function() {
-    this.completions = null; // reset completions
-
-    // asynchronously fetch history items
-    var port = chrome.extension.connect({ name: "getHistory" }) ;
-    var self = this;
-    port.onMessage.addListener(function(msg) {
-      var results = [];
-
-      for (var i = 0; i < msg.history.length; ++i) {
-        var historyItem = msg.history[i];
-        var title = '';
-
-        if (historyItem.title.length > 0)
-          title = ' <span class="title">' + historyItem.title + '</span>';
-
-        results.push({
-          str: '<em>history</em> ' + historyItem.url + title,
-          url: historyItem.url,
-        });
-      }
-      port = null;
-      self.readyCallback(results);
+    this.fetchFromPort('getHistory', { maxResults: this.maxResults }, function(msg) {
+      return msg.history.map(function(historyItem) {
+        return createUrlSuggestion('history', historyItem.url, historyItem.title);
+      });
     });
-    port.postMessage({ maxResults: this.maxEntries });
   }
 
   /** A fuzzy bookmark completer */
@@ -398,31 +417,12 @@ var completion = (function() {
   }
   FuzzyBookmarkCompleter.prototype = new AsyncFuzzyUrlCompleter;
   FuzzyBookmarkCompleter.prototype.refresh = function() {
-    this.completions = null; // reset completions
-
-    var port = chrome.extension.connect({ name: "getAllBookmarks" }) ;
-    var self = this;
-    port.onMessage.addListener(function(msg) {
-      var results = [];
-
-      for (var i = 0; i < msg.bookmarks.length; ++i) {
-        var bookmark = msg.bookmarks[i];
-        if (bookmark.url === undefined)
-          continue;
-
-        var title = '';
-        if (bookmark.title.length > 0)
-          title = ' <span class="title">' + bookmark.title + '</span>';
-
-        results.push({
-          str: '<em>bookmark</em> ' + bookmark.url + title,
-          url: bookmark.url,
-        });
-      }
-      port = null;
-      self.readyCallback(results);
+    this.fetchFromPort('getAllBookmarks', {}, function(msg) {
+      return msg.bookmarks.filter(function(bookmark) { return bookmark.url !== undefined })
+                          .map(function(bookmark) {
+        return createUrlSuggestion('bookmark', bookmark.url, bookmark.title);
+      })
     });
-    port.postMessage();
   }
 
   /** A fuzzy tab completer */
@@ -437,30 +437,13 @@ var completion = (function() {
     return [ open, open ];
   }
   FuzzyTabCompleter.prototype.refresh = function() {
-    this.completions = null; // reset completions
-
-    var port = chrome.extension.connect({ name: 'getTabsInCurrentWindow' }) ;
-    var self = this;
-    port.onMessage.addListener(function(msg) {
-      var results = [];
-
-      for (var i = 0; i < msg.tabs.length; ++i) {
-        var tab = msg.tabs[i];
-
-        var title = '';
-        if (tab.title.length > 0)
-          title = ' <span class="title">' + tab.title + '</span>';
-
-        results.push({
-          str: '<em>tab</em> ' + tab.url + title,
-          url: tab.url,
-          tab: tab,
-        });
-      }
-      port = null;
-      self.readyCallback(results);
+    this.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
+      return msg.tabs.map(function(tab) {
+        suggestion = createUrlSuggestion('tab', tab.url, tab.title);
+        suggestion.tab = tab;
+        return suggestion;
+      });
     });
-    port.postMessage();
   }
 
   /** A meta-completer that delegates queries and merges and sorts the results of a collection of other
@@ -470,16 +453,15 @@ var completion = (function() {
   }
   MergingCompleter.prototype = {
     refresh: function() {
-      for (var i = 0; i < this.sources.length; ++i)
-        this.sources[i].refresh();
+      this.sources.forEach(function(x) { x.refresh(); });
     },
 
     filter: function(query, callback) {
       var all = [];
       var counter = this.sources.length;
 
-      for (var i = 0; i < this.sources.length; ++i) {
-        this.sources[i].filter(query, function(results) {
+      this.sources.forEach(function(source) {
+        source.filter(query, function(results) {
           all = all.concat(results);
           if (--counter > 0)
             return;
@@ -490,7 +472,7 @@ var completion = (function() {
           });
           callback(all);
         });
-      }
+      });
     }
   }
 
-- 
cgit v1.2.3


From 82b461bbc0851bd3f6e3b3e8d3c4155e48400bcf Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 00:08:57 +0100
Subject: add bookmark in "all" completion

---
 fuzzyMode.js | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index a98e3f21..a7adec7a 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -22,6 +22,7 @@ var fuzzyMode = (function() {
     else if (name === 'all')
       return new completion.MergingCompleter([
         getCompleter('smart'),
+        getCompleter('bookmarks'),
         getCompleter('history'),
         getCompleter('tabs'),
         ]);
-- 
cgit v1.2.3


From f69fea31ad8c1e672f908fdf9debd64a5d0fee5e Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 00:17:30 +0100
Subject: more DRYing

---
 lib/completion.js | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 338ccbbb..35b1d132 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -83,9 +83,9 @@ var completion = (function() {
     /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
     self.cleanMatcherCache = function() {
       // remove old matchers
-      queries = Object.keys(self.matcherCache);
-      for (var i = 0; i < queries.length - self.matcherCacheSize; ++i)
+      Object.keys(self.matcherCache).forEach(function(query) {
         delete self.matcherCache(queries[i]);
+      });
     }
 
     /** Returns a regex that matches a string using a fuzzy :query. Example: The :query "abc" would result
@@ -95,6 +95,7 @@ var completion = (function() {
       query = self.normalize(query);
       if (!(query in self.matcherCache)) {
         // build up a regex for fuzzy matching
+        // TODO use an array and .join here
         var regex = '^';
         for (var i = 0; i < query.length; ++i)
           regex += '([^' + query[i] + ']*)(' + query[i] + ')';
@@ -108,8 +109,6 @@ var completion = (function() {
      * results of the last filtering are used as a starting point, instead of :source.
      */
     self.filter = function(query, source, getValue, id) {
-      var filtered = [];
-
       if (!(id in self.filterCache))
         self.filterCache[id] = {};
 
@@ -318,6 +317,8 @@ var completion = (function() {
 
     this.refresh = function() { };
 
+    // TODO make this shorter and use a more functional way to do it
+
     /** Checks if the input is a special command and if yes, add according suggestions to the given array */
     this.addCommandSuggestions = function(query, suggestions) {
       // check if the input is a special command
@@ -340,6 +341,7 @@ var completion = (function() {
         suggestions.push({
           render: createConstantFunction('<em>' + desc + '</em> ' + term),
           action: createActionOpenUrl(utils.createFullUrl(url)),
+          relevancy: -2, // this will appear even before the URL/search suggestion
         });
       }
     }
-- 
cgit v1.2.3


From 4edbe74415960b095185d4354e82f2171a9728da Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 18:38:22 +0100
Subject: fix small bug

---
 lib/completion.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/completion.js b/lib/completion.js
index 35b1d132..d36dc2e5 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -84,7 +84,7 @@ var completion = (function() {
     self.cleanMatcherCache = function() {
       // remove old matchers
       Object.keys(self.matcherCache).forEach(function(query) {
-        delete self.matcherCache(queries[i]);
+        delete self.matcherCache[query];
       });
     }
 
-- 
cgit v1.2.3


From a9d89d0aaa3e42904787666a6bcddb1521c32d7d Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 23:22:24 +0100
Subject: update results list asynchronously to take load from the CPU and
 improve the perceived responsiveness

---
 fuzzyMode.js | 36 +++++++++++++++++++++++++++++++-----
 1 file changed, 31 insertions(+), 5 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index a7adec7a..7716acfa 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -37,16 +37,19 @@ var fuzzyMode = (function() {
   function start(name, reverseAction) {
     var completer = getCompleter(name);
     if (!fuzzyBox)
-      fuzzyBox = new FuzzyBox(10);
+      fuzzyBox = new FuzzyBox(10, 300);
     completer.refresh();
     fuzzyBox.setCompleter(completer);
     fuzzyBox.show(reverseAction);
   }
 
   /** User interface for fuzzy completion */
-  var FuzzyBox = function(maxResults) {
+  var FuzzyBox = function(maxResults, refreshInterval) {
     this.prompt = '> ';
-    this.maxResults = maxResults || 10;
+    this.maxResults = maxResults;
+    this.refreshInterval = refreshInterval;
+    // query used to filter the last completion result. We need this for asynchronous updating
+    this.lastQuery = '';
     this.initDom();
     this.reset();
   }
@@ -72,7 +75,8 @@ var fuzzyMode = (function() {
       this.query = '';
       this.completions = [];
       this.selection = 0;
-      this.update();
+      // force synchronous updating so that the old results will not be flash up shortly
+      this.update(true);
     },
 
     updateSelection: function() {
@@ -129,6 +133,7 @@ var fuzzyMode = (function() {
 
       else if (keyChar.length == 1) {
         this.query += keyChar;
+
         this.update();
       }
 
@@ -137,10 +142,12 @@ var fuzzyMode = (function() {
       return true;
     },
 
-    update: function() {
+    updateInput: function() {
       this.query = this.query.replace(/^\s*/, '');
       this.input.textContent = this.query;
+    },
 
+    updateCompletions: function() {
       if (this.query.length == 0) {
         this.completionList.style.display = 'none';
         return;
@@ -164,6 +171,25 @@ var fuzzyMode = (function() {
       });
     },
 
+    update: function(sync) {
+      sync = sync || false; // explicitely default to asynchronous updating
+      this.updateInput();
+
+      if (sync) {
+        this.updateCompletions();
+      } else {
+        var self = this;
+        // always update asynchronously for better user experience and to take some load off the CPU
+        // (not every keystroke will cause a dedicated update)
+        setTimeout(function() {
+          if (self.query == self.lastQuery)
+            return;
+          self.lastQuery = self.query;
+          self.updateCompletions();
+        }, this.refreshInterval);
+      }
+    },
+
     initDom: function() {
       this.box = document.createElement('div');
       this.box.id = 'fuzzybox';
-- 
cgit v1.2.3


From 6463714d0f477b35d3d8f533eafbe980ada0bf05 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 23:28:33 +0100
Subject: fix small bug when closing and reopening dialog in combination with
 async updating

---
 fuzzyMode.js | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 7716acfa..9e3b09e0 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -48,8 +48,6 @@ var fuzzyMode = (function() {
     this.prompt = '> ';
     this.maxResults = maxResults;
     this.refreshInterval = refreshInterval;
-    // query used to filter the last completion result. We need this for asynchronous updating
-    this.lastQuery = '';
     this.initDom();
     this.reset();
   }
@@ -73,6 +71,8 @@ var fuzzyMode = (function() {
 
     reset: function() {
       this.query = '';
+      // query used to filter the last completion result. We need this for asynchronous updating
+      this.lastQuery = null;
       this.completions = [];
       this.selection = 0;
       // force synchronous updating so that the old results will not be flash up shortly
@@ -182,7 +182,7 @@ var fuzzyMode = (function() {
         // always update asynchronously for better user experience and to take some load off the CPU
         // (not every keystroke will cause a dedicated update)
         setTimeout(function() {
-          if (self.query == self.lastQuery)
+          if (self.query === self.lastQuery)
             return;
           self.lastQuery = self.query;
           self.updateCompletions();
-- 
cgit v1.2.3


From 9fd6faa0d5d0b9cda83e9595054c66822c2cbd72 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Tue, 24 Jan 2012 23:33:07 +0100
Subject: hide completion list if no completions are available

---
 fuzzyMode.js | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 9e3b09e0..c3b20096 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -152,7 +152,6 @@ var fuzzyMode = (function() {
         this.completionList.style.display = 'none';
         return;
       }
-      this.completionList.style.display = 'block';
 
       var self = this;
       this.completer.filter(this.query, function(completions) {
@@ -167,6 +166,8 @@ var fuzzyMode = (function() {
           li.innerHTML = completions[i].render();
           self.completionList.appendChild(li);
         }
+
+        self.completionList.style.display = completions.length > 0 ? 'block' : 'none';
         self.updateSelection();
       });
     },
-- 
cgit v1.2.3


From 3f1fa91d82c88e58273e4010f9b6dabc84088805 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:21:21 +0100
Subject: force update after pressing Return

---
 fuzzyMode.js | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index c3b20096..001bcb32 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -123,6 +123,8 @@ var fuzzyMode = (function() {
       // use primary action with Enter. Holding down Shift/Ctrl uses the alternative action
       // (opening in new tab)
       else if (event.keyCode == keyCodes.enter) {
+        this.update(true); // force synchronous update
+
         var alternative = (event.shiftKey || isPrimaryModifierKey(event));
         if (this.reverseAction)
           alternative = !alternative;
-- 
cgit v1.2.3


From 951a8535ced42904e97c88b97e98d303bf3672c2 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:22:38 +0100
Subject: code cleanup

---
 fuzzyMode.js | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 001bcb32..67a5e7d2 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -80,10 +80,9 @@ var fuzzyMode = (function() {
     },
 
     updateSelection: function() {
-      var items = this.completionList.childNodes;
-      for (var i = 0; i < items.length; ++i) {
-        items[i].className = (i == this.selection) ? 'selected' : '';
-      }
+      this.completionList.childNodes.forEach(function(child, i) {
+        child.className = (i == this.selection) ? 'selected' : '';
+      });
     },
 
     onKeydown: function(event) {
@@ -135,7 +134,6 @@ var fuzzyMode = (function() {
 
       else if (keyChar.length == 1) {
         this.query += keyChar;
-
         this.update();
       }
 
@@ -157,19 +155,14 @@ var fuzzyMode = (function() {
 
       var self = this;
       this.completer.filter(this.query, function(completions) {
+        self.completions = completions.slice(0, self.maxResults);
+
         // clear completions
-        self.completions = [];
-        while (self.completionList.hasChildNodes())
-          self.completionList.removeChild(self.completionList.firstChild);
-
-        for (var i = 0; i < completions.length && i < self.maxResults; ++i) {
-          self.completions.push(completions[i]);
-          var li = document.createElement('li');
-          li.innerHTML = completions[i].render();
-          self.completionList.appendChild(li);
-        }
+        self.completionList.innerHTML = self.completions.map(function(completion) {
+          return '<li>' + completion.render() + '</li>';
+        }).join('');
 
-        self.completionList.style.display = completions.length > 0 ? 'block' : 'none';
+        self.completionList.style.display = self.completions.length > 0 ? 'block' : 'none';
         self.updateSelection();
       });
     },
-- 
cgit v1.2.3


From f41ebfbe6bacbbeb4b1b532bd8d3f9623f91ee63 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:23:47 +0100
Subject: add HTML helpers

---
 lib/utils.js | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/lib/utils.js b/lib/utils.js
index a0ca9715..9b5cfcb9 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -20,6 +20,39 @@ var utils = {
     return func.apply(obj, argArray);
   },
 
+  /*
+   * Takes an array of XPath selectors, adds the necessary namespaces (currently only XHTML), and applies them
+   * to the document root. The namespaceResolver in evaluateXPath should be kept in sync with the namespaces
+   * here.
+   */
+  makeXPath: function(elementArray) {
+    var xpath = [];
+    for (var i in elementArray)
+      xpath.push("//" + elementArray[i], "//xhtml:" + elementArray[i]);
+    return xpath.join(" | ");
+  },
+
+  evaluateXPath: function(xpath, resultType) {
+    function namespaceResolver(namespace) {
+      return namespace == "xhtml" ? "http://www.w3.org/1999/xhtml" : null;
+    }
+    return document.evaluate(xpath, document.documentElement, namespaceResolver, resultType, null);
+  },
+
+  /** Creates a single DOM element from :html */
+  createElementFromHtml: function(html) {
+    var tmp = document.createElement("div");
+    tmp.innerHTML = html;
+    return tmp.firstChild;
+  },
+
+  /** Escapes HTML */
+  escapeHtml: function(html) {
+    var tmp = document.createElement("div");
+    tmp.textContent = html;
+    return tmp.innerHTML;
+  },
+
   /**
    * Generates a unique ID
    */
-- 
cgit v1.2.3


From 885c6333bc2b73c088f2de0c86ae760e0034491c Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:24:08 +0100
Subject: create DOM by HTML

---
 fuzzyMode.js | 35 +++++++++++------------------------
 1 file changed, 11 insertions(+), 24 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 67a5e7d2..8b817883 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -45,7 +45,7 @@ var fuzzyMode = (function() {
 
   /** User interface for fuzzy completion */
   var FuzzyBox = function(maxResults, refreshInterval) {
-    this.prompt = '> ';
+    this.prompt = '>';
     this.maxResults = maxResults;
     this.refreshInterval = refreshInterval;
     this.initDom();
@@ -187,30 +187,17 @@ var fuzzyMode = (function() {
     },
 
     initDom: function() {
-      this.box = document.createElement('div');
-      this.box.id = 'fuzzybox';
-      this.box.className = 'vimiumReset';
-
-      var inputBox = document.createElement('div');
-      inputBox.className = 'input';
-
-      var promptSpan = document.createElement('span');
-      promptSpan.className = 'prompt';
-      promptSpan.textContent = this.prompt;
-
-      this.input = document.createElement('span');
-      this.input.className = 'query';
-
-      inputBox.appendChild(promptSpan);
-      inputBox.appendChild(this.input);
-
-      this.completionList = document.createElement('ul');
-
-      this.box.appendChild(inputBox);
-      this.box.appendChild(this.completionList);
-
-      this.hide();
+      this.box = utils.createElementFromHtml(
+        '<div id="fuzzybox" class="vimiumReset">'+
+          '<div class="input">'+
+            '<span id="fuzzyboxPrompt" class="prompt">' + utils.escapeHtml(this.prompt) + '</span> '+
+            '<span id="fuzzyboxInput" class="query"></span></div>'+
+          '<ul id="fuzzyboxCompletions"></ul></div>');
+      this.box.style.display = 'none';
       document.body.appendChild(this.box);
+
+      this.input          = document.getElementById("fuzzyboxInput");
+      this.completionList = document.getElementById("fuzzyboxCompletions");
     },
   }
 
-- 
cgit v1.2.3


From 99c19d210f4f7024585eb93d80967377c67fa44e Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:30:36 +0100
Subject: fix regression in 10a77d25c3

---
 fuzzyMode.js | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8b817883..1edb18f0 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -80,9 +80,8 @@ var fuzzyMode = (function() {
     },
 
     updateSelection: function() {
-      this.completionList.childNodes.forEach(function(child, i) {
-        child.className = (i == this.selection) ? 'selected' : '';
-      });
+      for (var i = 0; i < this.completionList.children.length; ++i)
+        this.completionList.children[i].className = (i == this.selection) ? 'selected' : '';
     },
 
     onKeydown: function(event) {
-- 
cgit v1.2.3


From b226ddf11348660dc8e9f39dcf7346944082ff67 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:41:47 +0100
Subject: move query length threshold from UI to logic

This enables to set threshold to 0 for tabs (so that tabs are shown before typing).
---
 fuzzyMode.js      | 19 +++++--------------
 lib/completion.js | 13 +++++++++++--
 2 files changed, 16 insertions(+), 16 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 1edb18f0..cfa8656f 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -18,14 +18,14 @@ var fuzzyMode = (function() {
     else if (name === 'tabs')
       return new completion.FuzzyTabCompleter();
     else if (name === 'tabsSorted')
-      return new completion.MergingCompleter([getCompleter('tabs')]);
+      return new completion.MergingCompleter([getCompleter('tabs')], 0);
     else if (name === 'all')
       return new completion.MergingCompleter([
         getCompleter('smart'),
         getCompleter('bookmarks'),
         getCompleter('history'),
         getCompleter('tabs'),
-        ]);
+        ], 1);
   }
   function getCompleter(name) {
     if (!(name in completers))
@@ -49,7 +49,6 @@ var fuzzyMode = (function() {
     this.maxResults = maxResults;
     this.refreshInterval = refreshInterval;
     this.initDom();
-    this.reset();
   }
   FuzzyBox.prototype = {
     setCompleter: function(completer) {
@@ -141,17 +140,7 @@ var fuzzyMode = (function() {
       return true;
     },
 
-    updateInput: function() {
-      this.query = this.query.replace(/^\s*/, '');
-      this.input.textContent = this.query;
-    },
-
     updateCompletions: function() {
-      if (this.query.length == 0) {
-        this.completionList.style.display = 'none';
-        return;
-      }
-
       var self = this;
       this.completer.filter(this.query, function(completions) {
         self.completions = completions.slice(0, self.maxResults);
@@ -168,7 +157,9 @@ var fuzzyMode = (function() {
 
     update: function(sync) {
       sync = sync || false; // explicitely default to asynchronous updating
-      this.updateInput();
+
+      this.query = this.query.replace(/^\s*/, '');
+      this.input.textContent = this.query;
 
       if (sync) {
         this.updateCompletions();
diff --git a/lib/completion.js b/lib/completion.js
index d36dc2e5..b5793437 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -449,9 +449,13 @@ var completion = (function() {
   }
 
   /** A meta-completer that delegates queries and merges and sorts the results of a collection of other
-   * completer instances. */
-  var MergingCompleter = function(sources) {
+   * completer instances given in :sources. The optional argument :queryThreshold determines how long a
+   * query has to be to trigger a refresh. */
+  var MergingCompleter = function(sources, queryThreshold) {
+    if (queryThreshold === undefined)
+      queryThreshold = 1; // default
     this.sources = sources;
+    this.queryThreshold = queryThreshold;
   }
   MergingCompleter.prototype = {
     refresh: function() {
@@ -459,6 +463,11 @@ var completion = (function() {
     },
 
     filter: function(query, callback) {
+      if (query.length < this.queryThreshold) {
+        callback([]);
+        return;
+      }
+
       var all = [];
       var counter = this.sources.length;
 
-- 
cgit v1.2.3


From c397fffc94f563f1475f37c90eefa154ac78a6e0 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:47:39 +0100
Subject: prevent duplicate history items

---
 background_page.html | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/background_page.html b/background_page.html
index f220d76c..e248043c 100644
--- a/background_page.html
+++ b/background_page.html
@@ -332,7 +332,9 @@
 
   chrome.history.onVisited.addListener(function(item) {
     if (cachedHistory === null) return;
-    cachedHistory.push(item);
+    // only cache newly visited sites
+    if (item.visitCount === 1)
+      cachedHistory.push(item);
   });
 
   function getHistory(args, port) {
-- 
cgit v1.2.3


From ff8e8aa0e22a474b950b551259d330a7705514c3 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 00:54:53 +0100
Subject: make refresh interval configurable

For example, tab completion can happen instantly while history completion shouldn't.
---
 fuzzyMode.js | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index cfa8656f..87b4470a 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -34,20 +34,21 @@ var fuzzyMode = (function() {
   }
 
   /** Trigger the fuzzy mode dialog */
-  function start(name, reverseAction) {
+  function start(name, reverseAction, refreshInterval) {
     var completer = getCompleter(name);
     if (!fuzzyBox)
-      fuzzyBox = new FuzzyBox(10, 300);
+      fuzzyBox = new FuzzyBox(10);
     completer.refresh();
     fuzzyBox.setCompleter(completer);
+    fuzzyBox.setRefreshInterval(refreshInterval);
     fuzzyBox.show(reverseAction);
   }
 
   /** User interface for fuzzy completion */
-  var FuzzyBox = function(maxResults, refreshInterval) {
+  var FuzzyBox = function(maxResults) {
     this.prompt = '>';
     this.maxResults = maxResults;
-    this.refreshInterval = refreshInterval;
+    this.refreshInterval = 0;
     this.initDom();
   }
   FuzzyBox.prototype = {
@@ -56,6 +57,10 @@ var fuzzyMode = (function() {
       this.reset();
     },
 
+    setRefreshInterval: function(refreshInterval) {
+      this.refreshInterval = refreshInterval;
+    },
+
     show: function(reverseAction) {
       this.reverseAction = reverseAction;
       this.box.style.display = 'block';
@@ -193,9 +198,9 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activateAll:       function() { start('all',        false); },
-    activateAllNewTab: function() { start('all',        true);  },
-    activateTabs:      function() { start('tabsSorted', false); },
+    activateAll:       function() { start('all',        false, 300); },
+    activateAllNewTab: function() { start('all',        true,  300);  },
+    activateTabs:      function() { start('tabsSorted', false, 0); },
   }
 
 })();
-- 
cgit v1.2.3


From a0d0d8ecfe40a1b802f72dff100185875ee63e2f Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 01:21:56 +0100
Subject: make refresh <F5> work as expected

---
 fuzzyMode.js      |  1 +
 lib/completion.js | 15 ++++++++++++---
 2 files changed, 13 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 87b4470a..8d8f1412 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -119,6 +119,7 @@ var fuzzyMode = (function() {
       // refresh with F5
       else if (keyChar == 'f5') {
         this.completer.refresh();
+        this.lastQuery = null;
         this.update();
       }
 
diff --git a/lib/completion.js b/lib/completion.js
index b5793437..6aec9e83 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -104,6 +104,11 @@ var completion = (function() {
       return self.matcherCache[query];
     }
 
+    /** Clear the cache for the given source, e.g. for refreshing */
+    self.invalidateFilterCache = function(id) {
+      self.filterCache[id] = {};
+    }
+
     /** Filters a collection :source using fuzzy matching against an input string :query. If a query with
      * a less specific query was issued before (e.g. if the user added a letter to the query), the cached
      * results of the last filtering are used as a starting point, instead of :source.
@@ -251,9 +256,6 @@ var completion = (function() {
     this.extractStringFromMatch = function(match) { return stripHtmlTags(match.str); }
   }
   AsyncFuzzyUrlCompleter.prototype = {
-    // to be implemented by subclasses
-    refresh: function() { },
-
     calculateRelevancy: function(query, match) {
       return match.url.length /
         (fuzzyMatcher.calculateRelevancy(query, this.extractStringFromMatch(match)) + 1);
@@ -279,6 +281,10 @@ var completion = (function() {
       port.postMessage(query);
     },
 
+    resetCache: function() {
+      fuzzyMatcher.invalidateFilterCache(this.id);
+    },
+
     filter: function(query, callback) {
       var self = this;
 
@@ -406,6 +412,7 @@ var completion = (function() {
   }
   FuzzyHistoryCompleter.prototype = new AsyncFuzzyUrlCompleter;
   FuzzyHistoryCompleter.prototype.refresh = function() {
+    this.resetCache();
     this.fetchFromPort('getHistory', { maxResults: this.maxResults }, function(msg) {
       return msg.history.map(function(historyItem) {
         return createUrlSuggestion('history', historyItem.url, historyItem.title);
@@ -419,6 +426,7 @@ var completion = (function() {
   }
   FuzzyBookmarkCompleter.prototype = new AsyncFuzzyUrlCompleter;
   FuzzyBookmarkCompleter.prototype.refresh = function() {
+    this.resetCache();
     this.fetchFromPort('getAllBookmarks', {}, function(msg) {
       return msg.bookmarks.filter(function(bookmark) { return bookmark.url !== undefined })
                           .map(function(bookmark) {
@@ -439,6 +447,7 @@ var completion = (function() {
     return [ open, open ];
   }
   FuzzyTabCompleter.prototype.refresh = function() {
+    this.resetCache();
     this.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
       return msg.tabs.map(function(tab) {
         suggestion = createUrlSuggestion('tab', tab.url, tab.title);
-- 
cgit v1.2.3


From d761e429f7c6b8583d32f7849fdbeb9aa2b50faf Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 01:22:19 +0100
Subject: introduce a utils helper for prototype inheritance

---
 lib/completion.js | 6 +++---
 lib/utils.js      | 8 ++++++++
 2 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 6aec9e83..3c43f28b 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -410,7 +410,7 @@ var completion = (function() {
     AsyncFuzzyUrlCompleter.call(this);
     this.maxResults = maxResults || 1000;
   }
-  FuzzyHistoryCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  utils.extend(AsyncFuzzyUrlCompleter, FuzzyHistoryCompleter);
   FuzzyHistoryCompleter.prototype.refresh = function() {
     this.resetCache();
     this.fetchFromPort('getHistory', { maxResults: this.maxResults }, function(msg) {
@@ -424,7 +424,7 @@ var completion = (function() {
   var FuzzyBookmarkCompleter = function() {
     AsyncFuzzyUrlCompleter.call(this);
   }
-  FuzzyBookmarkCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  utils.extend(AsyncFuzzyUrlCompleter, FuzzyBookmarkCompleter);
   FuzzyBookmarkCompleter.prototype.refresh = function() {
     this.resetCache();
     this.fetchFromPort('getAllBookmarks', {}, function(msg) {
@@ -439,7 +439,7 @@ var completion = (function() {
   var FuzzyTabCompleter = function() {
     AsyncFuzzyUrlCompleter.call(this);
   }
-  FuzzyTabCompleter.prototype = new AsyncFuzzyUrlCompleter;
+  utils.extend(AsyncFuzzyUrlCompleter, FuzzyTabCompleter);
   FuzzyTabCompleter.prototype.createAction = function(match) {
     var open = function() {
       chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: match.tab.id });
diff --git a/lib/utils.js b/lib/utils.js
index 9b5cfcb9..7ed7c9ad 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -39,6 +39,14 @@ var utils = {
     return document.evaluate(xpath, document.documentElement, namespaceResolver, resultType, null);
   },
 
+  /** Sets up prototype inheritance */
+  extend: function(base, sub) {
+    function surrogateCtor() { }
+    surrogateCtor.prototype = base.prototype;
+    sub.prototype = new surrogateCtor();
+    sub.prototype.constructor = sub;
+  },
+
   /** Creates a single DOM element from :html */
   createElementFromHtml: function(html) {
     var tmp = document.createElement("div");
-- 
cgit v1.2.3


From 386c08403503ffad5e08e4f554529c248fdaa8bc Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 01:53:41 +0100
Subject: code cleanup + small bugfixes

---
 lib/completion.js | 123 +++++++++++++++++++-----------------------------------
 1 file changed, 44 insertions(+), 79 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 3c43f28b..a2f97c2c 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -153,10 +153,10 @@ var completion = (function() {
     return self;
   })();
 
-  /** Strips HTML tags using a naive regex replacement. Optionally, saves the stripped HTML tags in a
-   * dictionary indexed by the position where the tag should be reinserted. */
+  /** Strips HTML tags and escape sequences using a naive regex replacement. Optionally, saves the stripped
+   * HTML tags in a dictionary indexed by the position where the tag should be reinserted. */
   function stripHtmlTags(str, positions) {
-    var result = str.replace(/<[^>]*>/g, '');
+    var result = str.replace(/<[^>]*>|&[a-z]+;/gi, '');
     if (!positions)
       return result;
 
@@ -240,6 +240,14 @@ var completion = (function() {
     }
   }
 
+  /** Creates an file-internal representation of a URL match with the given paramters */
+  function createCompletionHtml(type, url, title) {
+    title = title || '';
+    // sanitize input, it could come from a malicious web site
+    title = title.length > 0 ? ' <span class="title">' + utils.escapeHtml(title) + '</span>' : '';
+    return '<em>' + type + '</em> ' + utils.escapeHtml(url) + title;
+  }
+
   /** Creates a function that returns a constant value */
   function createConstantFunction(x) {
     return function() { return x; }
@@ -323,88 +331,43 @@ var completion = (function() {
 
     this.refresh = function() { };
 
-    // TODO make this shorter and use a more functional way to do it
-
-    /** Checks if the input is a special command and if yes, add according suggestions to the given array */
-    this.addCommandSuggestions = function(query, suggestions) {
-      // check if the input is a special command
-      for (var i = 0; i < commandKeys.length; ++i) {
-        var key = commandKeys[i];
-        if (query.indexOf(key) != 0)
-          continue;
-
-        var term = query.slice(key.length, query.length);
-        var command = commands[key];
-        var desc = command[0];
-        var pattern = command[1];
-        var url;
+    /** Returns the suggestions matching the user-defined commands */
+    this.getCommandSuggestions = function(query, suggestions) {
+      return commandKeys.filter(function(cmd) { return query.indexOf(cmd) == 0 }).map(function(cmd) {
+        var term = query.slice(cmd.length);
+        var desc = commands[cmd][0];
+        var pattern = commands[cmd][1];
+        var url = typeof pattern == 'function' ? pattern(term) : pattern.replace(/%s/g, term);
 
-        if (typeof pattern === 'function')
-          url = pattern(term);
-        else
-          url = pattern.replace(/%s/g, term);
-
-        suggestions.push({
-          render: createConstantFunction('<em>' + desc + '</em> ' + term),
+        return {
+          render: function() { return createCompletionHtml(desc, term) },
           action: createActionOpenUrl(utils.createFullUrl(url)),
-          relevancy: -2, // this will appear even before the URL/search suggestion
-        });
-      }
+          relevancy: -2 // this will appear even before the URL/search suggestion
+        };
+      });
     }
 
-    /** Checks if the input is a URL. If yes, add the URL to the list of suggestions. If no, add a search
-     * query to the list of suggestions. */
-    this.addUrlOrSearchSuggestion = function(query, suggestions) {
-      var url, str;
-
+    /** Checks if the input is a URL. If yes, returns a suggestion to visit it. If no, returns a suggestion
+     * to start a web search. */
+    this.getUrlOrSearchSuggestions = function(query, suggestions) {
       // trim query
       query = query.replace(/^\s+|\s+$/g, '');
-      // TODO fix HTML injection
-      if (utils.isUrl(query)) {
-        url = utils.createFullUrl(query);
-        str = '<em>goto</em> ' + query;
-      } else {
-        url = utils.createSearchUrl(query);
-        str = '<em>search</em> ' + query;
-      }
-      suggestions.push({
-        render: function() { return str; },
-        action: createActionOpenUrl(url),
-        // relevancy will always be the lowest one, so the suggestion is at the top
-        relevancy: -1,
-      });
+      var isUrl = utils.isUrl(query);
+
+      return [{
+        render: function() { return createCompletionHtml(isUrl ? 'goto' : 'search', query); },
+        action: createActionOpenUrl(isUrl ? utils.createFullUrl(query)
+                                          : utils.createSearchUrl(query)),
+        relevancy: -1, // low relevancy so this should appear at the top
+      }];
     }
 
     this.filter = function(query, callback) {
-      var suggestions = [];
-      this.addCommandSuggestions(query, suggestions);
-      this.addUrlOrSearchSuggestion(query, suggestions);
-      callback(suggestions);
-    };
-  }
-
-  // TODO fix HTML injection
-  function createUrlSuggestion(type, url, title) {
-    title = title.length > 0 ? ' <span class="title">' + title + '</span>' : '';
-    return { str: '<em>' + type + '</em> ' + url + title,
-             url: url };
+      callback(this.getCommandSuggestions(query).concat(
+               this.getUrlOrSearchSuggestions(query)));
+    }
   }
 
-  /** Convenience function to remove shared code in the completers. Clear the completion cache, sends
-    * a message to an extension port and pipes the returned message through a callback before storing it into
-    * the instance's completion cache.
-    */
-  function fetchFromPort(self, name, query, callback) {
-    self.completions = null; // reset completions
-
-    // asynchronously fetch from a port
-    var port = chrome.extension.connect({ name: name }) ;
-    port.onMessage.addListener(function(msg) {
-      self.readyCallback(callback(msg));
-    });
-    port.postMessage(query);
-  };
-
   /** A fuzzy history completer */
   var FuzzyHistoryCompleter = function(maxResults) {
     AsyncFuzzyUrlCompleter.call(this);
@@ -415,7 +378,8 @@ var completion = (function() {
     this.resetCache();
     this.fetchFromPort('getHistory', { maxResults: this.maxResults }, function(msg) {
       return msg.history.map(function(historyItem) {
-        return createUrlSuggestion('history', historyItem.url, historyItem.title);
+        return { str: createCompletionHtml('history', historyItem.url, historyItem.title),
+                 url: historyItem.url };
       });
     });
   }
@@ -430,7 +394,8 @@ var completion = (function() {
     this.fetchFromPort('getAllBookmarks', {}, function(msg) {
       return msg.bookmarks.filter(function(bookmark) { return bookmark.url !== undefined })
                           .map(function(bookmark) {
-        return createUrlSuggestion('bookmark', bookmark.url, bookmark.title);
+        return { str: createCompletionHtml('bookmark', bookmark.url, bookmark.title),
+                 url: bookmark.url };
       })
     });
   }
@@ -450,9 +415,9 @@ var completion = (function() {
     this.resetCache();
     this.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
       return msg.tabs.map(function(tab) {
-        suggestion = createUrlSuggestion('tab', tab.url, tab.title);
-        suggestion.tab = tab;
-        return suggestion;
+        return { str: createCompletionHtml('tab', tab.url, tab.title),
+                 url: tab.url,
+                 tab: tab };
       });
     });
   }
-- 
cgit v1.2.3


From ccd7998112740e8f19efd2bdcab0be1c2b04bbc7 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 02:04:11 +0100
Subject: correctly handle selection after refresh

---
 fuzzyMode.js | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8d8f1412..e927a0a4 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -84,6 +84,7 @@ var fuzzyMode = (function() {
     },
 
     updateSelection: function() {
+      this.selection = Math.min(this.selection, this.completions.length - 1)
       for (var i = 0; i < this.completionList.children.length; ++i)
         this.completionList.children[i].className = (i == this.selection) ? 'selected' : '';
     },
-- 
cgit v1.2.3


From 4cfe44bb597d49bb853a207072d064283f118ec4 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 02:29:38 +0100
Subject: fix HTML tag stripping

---
 lib/completion.js | 27 ++++++++++++++-------------
 1 file changed, 14 insertions(+), 13 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index a2f97c2c..2163dbdd 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -153,23 +153,24 @@ var completion = (function() {
     return self;
   })();
 
+  var htmlRegex = /<[^>]*>|&[a-z]+;/gi;
+
   /** Strips HTML tags and escape sequences using a naive regex replacement. Optionally, saves the stripped
    * HTML tags in a dictionary indexed by the position where the tag should be reinserted. */
   function stripHtmlTags(str, positions) {
-    var result = str.replace(/<[^>]*>|&[a-z]+;/gi, '');
     if (!positions)
-      return result;
-
-    // we need to get information about where the tags can be reinserted after some string processing
-    var start;
-    var end = -1;
-    var stripped = 0;
-    while (0 <= (start = str.indexOf('<', end + 1))) {
-      end = str.indexOf('>', start);
-      positions[start - stripped] = str.slice(start, end + 1);
-      stripped += end - start + 1;
-    }
-    return result;
+      return str.replace(htmlRegex, '');
+
+    var match = str.match(htmlRegex).reverse();
+    var split = str.split(htmlRegex);
+    var offset = 0;
+    var i = 0;
+    split.forEach(function(text) {
+      if (match.length > 0)
+        positions[offset += text.length] = match.pop();
+    });
+
+    return split.join('');
   }
 
   /** Creates an action that opens :url in the current tab by default or in a new tab as an alternative. */
-- 
cgit v1.2.3


From d1364c2dffe7e371c60fede5007b886fb7c9beb3 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 02:35:50 +0100
Subject: make fuzzybox HTML more compact

---
 fuzzyMode.js | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index e927a0a4..8c71107b 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -187,14 +187,14 @@ var fuzzyMode = (function() {
       this.box = utils.createElementFromHtml(
         '<div id="fuzzybox" class="vimiumReset">'+
           '<div class="input">'+
-            '<span id="fuzzyboxPrompt" class="prompt">' + utils.escapeHtml(this.prompt) + '</span> '+
-            '<span id="fuzzyboxInput" class="query"></span></div>'+
-          '<ul id="fuzzyboxCompletions"></ul></div>');
+            '<span class="prompt">' + utils.escapeHtml(this.prompt) + '</span> '+
+            '<span class="query"></span></div>'+
+          '<ul></ul></div>');
       this.box.style.display = 'none';
       document.body.appendChild(this.box);
 
-      this.input          = document.getElementById("fuzzyboxInput");
-      this.completionList = document.getElementById("fuzzyboxCompletions");
+      this.input          = document.querySelector("#fuzzybox .query");
+      this.completionList = document.querySelector("#fuzzybox ul");
     },
   }
 
-- 
cgit v1.2.3


From 66330ac3b5f4320ddf3d7c985f351eaa6886a9da Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 17:30:51 +0100
Subject: rename "match" method to prevent confusion

---
 lib/completion.js | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 2163dbdd..6f5b0f96 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -32,7 +32,7 @@ var completion = (function() {
      *
      * _Don't use this to check if a string matches a query_. Use `getMatcher(query).test(str)` instead.
      */
-    self.match = function(query, str) {
+    self.getMatchGroups = function(query, str) {
       query = self.normalize(query);
       if (query.length == 0)
         return str.length ? [str] : [];
@@ -49,7 +49,7 @@ var completion = (function() {
           continue;
 
         // we use recursive backtracking here, this is why it's slow.
-        rest = self.match(query.slice(i), str.slice(partOffset + i));
+        rest = self.getMatchGroups(query.slice(i), str.slice(partOffset + i));
         if (!rest) continue;
 
         return [
@@ -202,7 +202,7 @@ var completion = (function() {
         // tags and reinsert them after the matching process
         var htmlTags = {};
         str = stripHtmlTags(str, htmlTags);
-        var groups = fuzzyMatcher.match(query, str);
+        var groups = fuzzyMatcher.getMatchGroups(query, str);
         var html = '';
         var htmlOffset = 0;
 
-- 
cgit v1.2.3


From b23ec4bafe188dc584ebd2b674566d429198ae09 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 17:36:31 +0100
Subject: fix small bug with selected item

---
 fuzzyMode.js | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8c71107b..29268505 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -84,7 +84,8 @@ var fuzzyMode = (function() {
     },
 
     updateSelection: function() {
-      this.selection = Math.min(this.selection, this.completions.length - 1)
+      if (this.completions.length > 0)
+        this.selection = Math.min(this.selection, this.completions.length - 1);
       for (var i = 0; i < this.completionList.children.length; ++i)
         this.completionList.children[i].className = (i == this.selection) ? 'selected' : '';
     },
-- 
cgit v1.2.3


From 76b981c5a3195eac12054afe2534645cd7610d30 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 17:53:48 +0100
Subject: fix a bug in the filtering algo that causes caching not to happen

---
 lib/completion.js | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 6f5b0f96..68f8d4bf 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -117,8 +117,8 @@ var completion = (function() {
       if (!(id in self.filterCache))
         self.filterCache[id] = {};
 
-      // find the most specific list of results in the cache
-      var maxSpecificity = 0;
+      // find the most narrow list of results in the cache
+      var optSpecificity = source.length;
       var specificity;
       for (key in self.filterCache[id]) {
         if (!self.filterCache[id].hasOwnProperty(key))
@@ -130,11 +130,15 @@ var completion = (function() {
           continue;
         }
 
+        // is this a plausible result set to use as a source?
+        if (query.indexOf(key) < 0)
+          continue;
+
         // is this cache entry the most specific so far?
         specificity = self.filterCache[id][key].length;
-        if (query.indexOf(key) == 0 && specificity > maxSpecificity) {
+        if (specificity < optSpecificity) {
           source = self.filterCache[id][key];
-          maxSpecificity = specificity;
+          optSpecificity = specificity;
         }
       }
 
-- 
cgit v1.2.3


From 7c2755bcd67968f9646ac3b79432bf45da349246 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 17:58:06 +0100
Subject: sort history by last visit time and raise number of history items to
 be searched

---
 background_page.html | 3 +--
 fuzzyMode.js         | 2 +-
 2 files changed, 2 insertions(+), 3 deletions(-)

diff --git a/background_page.html b/background_page.html
index e248043c..b6b72406 100644
--- a/background_page.html
+++ b/background_page.html
@@ -322,8 +322,7 @@
     }, function(history) {
       // sorting in ascending order, so we can push new items to the end later
       history.sort(function(a, b) {
-        // visitCount may be undefined
-        return (a.visitCount || 0) - (b.visitCount || 0);
+        return (a.lastVisitTime|| 0) - (b.lastVisitTime || 0);
       });
       cachedHistory = history;
       callback(cachedHistory);
diff --git a/fuzzyMode.js b/fuzzyMode.js
index 29268505..cbefcde4 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -12,7 +12,7 @@ var fuzzyMode = (function() {
         '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         });
     else if (name === 'history')
-      return new completion.FuzzyHistoryCompleter(1500);
+      return new completion.FuzzyHistoryCompleter(2000);
     else if (name === 'bookmarks')
       return new completion.FuzzyBookmarkCompleter();
     else if (name === 'tabs')
-- 
cgit v1.2.3


From e8b402595e5e7ebeb5abc6e1d058692370369cad Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 21:52:15 +0100
Subject: fix bug when history maxResults is too high

---
 background_page.html | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/background_page.html b/background_page.html
index b6b72406..a56028bc 100644
--- a/background_page.html
+++ b/background_page.html
@@ -339,7 +339,7 @@
   function getHistory(args, port) {
     useHistory(function(history) {
       port.postMessage({
-        history: history.slice(history.length - args.maxResults)
+        history: history.slice(Math.max(history.length - args.maxResults, 0))
       });
     });
   };
-- 
cgit v1.2.3


From 392232f5756f095dca0329dfd7ce3ae0752245ec Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 22:03:26 +0100
Subject: add lazy evaluation at several places

---
 fuzzyMode.js      |   8 +-
 lib/completion.js | 256 +++++++++++++++++++++++++++++-------------------------
 2 files changed, 140 insertions(+), 124 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index cbefcde4..04fa2666 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -150,12 +150,12 @@ var fuzzyMode = (function() {
 
     updateCompletions: function() {
       var self = this;
-      this.completer.filter(this.query, function(completions) {
-        self.completions = completions.slice(0, self.maxResults);
+      this.completer.filter(this.query, this.maxResults, function(completions) {
+        self.completions = completions;
 
         // clear completions
-        self.completionList.innerHTML = self.completions.map(function(completion) {
-          return '<li>' + completion.render() + '</li>';
+        self.completionList.innerHTML = completions.map(function(completion) {
+          return '<li>' + completion.html + '</li>';
         }).join('');
 
         self.completionList.style.display = self.completions.length > 0 ? 'block' : 'none';
diff --git a/lib/completion.js b/lib/completion.js
index 68f8d4bf..1915a83a 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -195,62 +195,54 @@ var completion = (function() {
       return [ open(false), open(true, true), open(true, false) ];
   }
 
-  /** Creates a completion that renders by marking fuzzy-matched parts. */
-  function createHighlightingCompletion(query, str, action, relevancy) {
-    return {
-      action: action,
-      relevancy: relevancy,
-
-      render: function() {
-        // we want to match the content in HTML tags, but not the HTML tags themselves, so we remove the
-        // tags and reinsert them after the matching process
-        var htmlTags = {};
-        str = stripHtmlTags(str, htmlTags);
-        var groups = fuzzyMatcher.getMatchGroups(query, str);
-        var html = '';
-        var htmlOffset = 0;
-
-        // this helper function adds the HTML generated _for one single character_ to the HTML output
-        // and reinserts HTML tags stripped before, if they were at this position
-        function addToHtml(str) {
-          if (htmlOffset in htmlTags)
-            html += htmlTags[htmlOffset];
-          html += str;
-          ++htmlOffset;
-        }
-
-        function addCharsWithDecoration(str, before, after) {
-          before = before || '';
-          after = after || '';
-          for (var i = 0; i < str.length; ++i)
-            addToHtml(before + str[i] + after);
-        }
-
-        // iterate over the match groups. They are non-matched and matched string parts, in alternating order
-        for (var i = 0; i < groups.length; ++i) {
-          if (i % 2 == 0)
-            // we have a non-matched part, it could have several characters. We need to insert them character
-            // by character, so that addToHtml can keep track of the position in the original string
-            addCharsWithDecoration(groups[i]);
-          else
-            // we have a matched part. In addition to the characters themselves, we add some decorating HTML.
-            addCharsWithDecoration(groups[i], '<span class="fuzzyMatch">', '</span>');
-        };
-
-        // call it another time so that a tag at the very last position is reinserted
-        addToHtml('');
-
-        return html;
-      },
-    }
-  }
-
   /** Creates an file-internal representation of a URL match with the given paramters */
-  function createCompletionHtml(type, url, title) {
+  function createCompletionHtml(type, str, title) {
     title = title || '';
     // sanitize input, it could come from a malicious web site
     title = title.length > 0 ? ' <span class="title">' + utils.escapeHtml(title) + '</span>' : '';
-    return '<em>' + type + '</em> ' + utils.escapeHtml(url) + title;
+    return '<em>' + type + '</em> ' + utils.escapeHtml(str) + title;
+  }
+
+  /** Renders a completion by marking fuzzy-matched parts. */
+  function renderFuzzy(query, html) {
+    // we want to match the content in HTML tags, but not the HTML tags themselves, so we remove the
+    // tags and reinsert them after the matching process
+    var htmlTags = {};
+    var groups = fuzzyMatcher.getMatchGroups(query, stripHtmlTags(html, htmlTags));
+
+    html = [];
+    var htmlOffset = 0;
+
+    // this helper function adds the HTML generated _for one single character_ to the HTML output
+    // and reinserts HTML tags stripped before, if they were at this position
+    function addToHtml(str) {
+      if (htmlOffset in htmlTags)
+        html.push(htmlTags[htmlOffset]);
+      html.push(str);
+      ++htmlOffset;
+    }
+
+    function addCharsWithDecoration(str, before, after) {
+      before = before || '';
+      after = after || '';
+      for (var i = 0; i < str.length; ++i)
+        addToHtml(before + str[i] + after);
+    }
+
+    // iterate over the match groups. They are non-matched and matched string parts, in alternating order
+    for (var i = 0; i < groups.length; ++i) {
+      if (i % 2 == 0)
+        // we have a non-matched part, it could have several characters. We need to insert them character
+        // by character, so that addToHtml can keep track of the position in the original string
+        addCharsWithDecoration(groups[i]);
+      else
+        // we have a matched part. In addition to the characters themselves, we add some decorating HTML.
+        addCharsWithDecoration(groups[i], '<span class="fuzzyMatch">', '</span>');
+    };
+
+    // call it another time so that a tag at the very last position is reinserted
+    addToHtml('');
+    return html.join('');
   }
 
   /** Creates a function that returns a constant value */
@@ -258,27 +250,24 @@ var completion = (function() {
     return function() { return x; }
   }
 
+  /** A completion class that only holds a relevancy value and a function to get HTML and action
+   * properties */
+  var LazyCompletion = function(relevancy, builder) {
+    this.relevancy = relevancy;
+    this.build = builder;
+  }
+
   /** Helper class to construct fuzzy completers for asynchronous data sources like history or bookmark
    * matchers. */
-  var AsyncFuzzyUrlCompleter = function() {
+  var AsyncCompleter = function() {
     this.completions = null;
     this.id = utils.createUniqueId();
     this.readyCallback = this.fallbackReadyCallback = function(results) {
       this.completions = results;
     }
-    this.extractStringFromMatch = function(match) { return stripHtmlTags(match.str); }
   }
-  AsyncFuzzyUrlCompleter.prototype = {
-    calculateRelevancy: function(query, match) {
-      return match.url.length /
-        (fuzzyMatcher.calculateRelevancy(query, this.extractStringFromMatch(match)) + 1);
-    },
-
-    createAction: function(match) {
-      return createActionOpenUrl(match.url);
-    },
-
-    /** Convenience function to remove shared code in the completers. Clear the completion cache, sends
+  AsyncCompleter.prototype = {
+    /** Convenience function to remove shared code in the completers. Clears the completion cache, sends
      * a message to an extension port and pipes the returned message through a callback before storing it into
      * the instance's completion cache.
      */
@@ -298,17 +287,44 @@ var completion = (function() {
       fuzzyMatcher.invalidateFilterCache(this.id);
     },
 
+    /** Convenience function to remove shared code in the completers. Creates an internal representation of
+     * a fuzzy completion item that is still independent of the query. The bind function will be called with
+     * the actual query as an argument later. */
+    createInternalMatch: function(type, item, action) {
+      var url = item.url;
+      var parts = [type, url, item.title];
+      var str = parts.join(' ');
+      action = action || createActionOpenUrl(url);
+
+      function createLazyCompletion(query) {
+        return new LazyCompletion(url.length / fuzzyMatcher.calculateRelevancy(query, str), function() {
+          return {
+            html:   renderFuzzy(query, createCompletionHtml.apply(null, parts)),
+            action: action,
+          }});
+      }
+
+      // add one more layer of indirection: For filtering, we only need the string to match.
+      // Only after we reduced the number of possible results, we call :bind on them to get
+      // an actual completion object
+      return {
+        str: parts.join(' '),
+        bind: createLazyCompletion,
+      }
+    },
+
+    // Default to handle results using fuzzy matching. This can be overridden by subclasses.
+    processResults: function(query, results) {
+      results = fuzzyMatcher.filter(query, results, function(match) { return match.str }, this.id);
+      // bind the query-agnostic, lazy results to a query
+      return results.map(function(result) { return result.bind(query); });
+    },
+
     filter: function(query, callback) {
       var self = this;
 
       var handler = function(results) {
-        var filtered = fuzzyMatcher.filter(query, results, self.extractStringFromMatch, self.id);
-        callback(filtered.map(function(match) {
-          return createHighlightingCompletion(
-                query, match.str,
-                self.createAction(match),
-                self.calculateRelevancy(query, match));
-        }));
+        callback(self.processResults(query, results));
       }
 
       // are the results ready?
@@ -319,8 +335,8 @@ var completion = (function() {
         // no: register the handler as a callback
         this.readyCallback = function(results) {
           handler(results);
-          this.readyCallback = this.fallbackReadyCallback;
-          this.readyCallback(results);
+          self.readyCallback = self.fallbackReadyCallback;
+          self.readyCallback(results);
         }
       }
     },
@@ -344,85 +360,86 @@ var completion = (function() {
         var pattern = commands[cmd][1];
         var url = typeof pattern == 'function' ? pattern(term) : pattern.replace(/%s/g, term);
 
-        return {
-          render: function() { return createCompletionHtml(desc, term) },
-          action: createActionOpenUrl(utils.createFullUrl(url)),
-          relevancy: -2 // this will appear even before the URL/search suggestion
-        };
+        // this will appear even before the URL/search suggestion
+        return new LazyCompletion(-2, function() {
+          return {
+            html:   createCompletionHtml(desc, term),
+            action: createActionOpenUrl(utils.createFullUrl(url)),
+          }})
       });
     }
 
     /** Checks if the input is a URL. If yes, returns a suggestion to visit it. If no, returns a suggestion
      * to start a web search. */
-    this.getUrlOrSearchSuggestions = function(query, suggestions) {
+    this.getUrlOrSearchSuggestion = function(query, suggestions) {
       // trim query
       query = query.replace(/^\s+|\s+$/g, '');
       var isUrl = utils.isUrl(query);
 
-      return [{
-        render: function() { return createCompletionHtml(isUrl ? 'goto' : 'search', query); },
-        action: createActionOpenUrl(isUrl ? utils.createFullUrl(query)
-                                          : utils.createSearchUrl(query)),
-        relevancy: -1, // low relevancy so this should appear at the top
-      }];
+      return new LazyCompletion(-1, function() {
+        return {
+          html: createCompletionHtml(isUrl ? 'goto' : 'search', query),
+          action: createActionOpenUrl(isUrl ? utils.createFullUrl(query)
+                                            : utils.createSearchUrl(query)),
+        }});
     }
 
     this.filter = function(query, callback) {
-      callback(this.getCommandSuggestions(query).concat(
-               this.getUrlOrSearchSuggestions(query)));
+      suggestions = this.getCommandSuggestions(query);
+      suggestions.push(this.getUrlOrSearchSuggestion(query));
+      callback(suggestions);
     }
   }
 
   /** A fuzzy history completer */
   var FuzzyHistoryCompleter = function(maxResults) {
-    AsyncFuzzyUrlCompleter.call(this);
+    AsyncCompleter.call(this);
     this.maxResults = maxResults || 1000;
   }
-  utils.extend(AsyncFuzzyUrlCompleter, FuzzyHistoryCompleter);
+  utils.extend(AsyncCompleter, FuzzyHistoryCompleter);
+
   FuzzyHistoryCompleter.prototype.refresh = function() {
-    this.resetCache();
-    this.fetchFromPort('getHistory', { maxResults: this.maxResults }, function(msg) {
-      return msg.history.map(function(historyItem) {
-        return { str: createCompletionHtml('history', historyItem.url, historyItem.title),
-                 url: historyItem.url };
+    var self = this;
+    self.resetCache();
+    self.fetchFromPort('getHistory', { maxResults: self.maxResults }, function(msg) {
+      return msg.history.map(function(item) {
+        return self.createInternalMatch('history', item);
       });
     });
   }
 
   /** A fuzzy bookmark completer */
   var FuzzyBookmarkCompleter = function() {
-    AsyncFuzzyUrlCompleter.call(this);
+    AsyncCompleter.call(this);
   }
-  utils.extend(AsyncFuzzyUrlCompleter, FuzzyBookmarkCompleter);
+  utils.extend(AsyncCompleter, FuzzyBookmarkCompleter);
+
   FuzzyBookmarkCompleter.prototype.refresh = function() {
-    this.resetCache();
-    this.fetchFromPort('getAllBookmarks', {}, function(msg) {
+    var self = this;
+    self.resetCache();
+    self.fetchFromPort('getAllBookmarks', {}, function(msg) {
       return msg.bookmarks.filter(function(bookmark) { return bookmark.url !== undefined })
                           .map(function(bookmark) {
-        return { str: createCompletionHtml('bookmark', bookmark.url, bookmark.title),
-                 url: bookmark.url };
-      })
+        return self.createInternalMatch('bookmark', bookmark);
+      });
     });
   }
 
   /** A fuzzy tab completer */
   var FuzzyTabCompleter = function() {
-    AsyncFuzzyUrlCompleter.call(this);
-  }
-  utils.extend(AsyncFuzzyUrlCompleter, FuzzyTabCompleter);
-  FuzzyTabCompleter.prototype.createAction = function(match) {
-    var open = function() {
-      chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: match.tab.id });
-    }
-    return [ open, open ];
+    AsyncCompleter.call(this);
   }
+  utils.extend(AsyncCompleter, FuzzyTabCompleter);
+
   FuzzyTabCompleter.prototype.refresh = function() {
-    this.resetCache();
-    this.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
+    var self = this;
+    self.resetCache();
+    self.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
       return msg.tabs.map(function(tab) {
-        return { str: createCompletionHtml('tab', tab.url, tab.title),
-                 url: tab.url,
-                 tab: tab };
+        var open = function() {
+          chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: tab.id });
+        }
+        return self.createInternalMatch('tab', tab, [open, open, open]);
       });
     });
   }
@@ -441,7 +458,7 @@ var completion = (function() {
       this.sources.forEach(function(x) { x.refresh(); });
     },
 
-    filter: function(query, callback) {
+    filter: function(query, maxResults, callback) {
       if (query.length < this.queryThreshold) {
         callback([]);
         return;
@@ -457,10 +474,9 @@ var completion = (function() {
             return;
 
           // all sources have provided results by now, so we can sort and return
-          all.sort(function(a,b) {
-            return a.relevancy - b.relevancy;
-          });
-          callback(all);
+          all.sort(function(a,b) { return a.relevancy - b.relevancy; });
+          // evalulate lazy completions for the top n results
+          callback(all.slice(0, maxResults).map(function(result) { return result.build(); }));
         });
       });
     }
-- 
cgit v1.2.3


From f7f40e3dc9ad17618e8b485b061e958b7338c486 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 22:19:24 +0100
Subject: raise number of history items searched

---
 fuzzyMode.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 04fa2666..a2ff7dc5 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -12,7 +12,7 @@ var fuzzyMode = (function() {
         '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
         });
     else if (name === 'history')
-      return new completion.FuzzyHistoryCompleter(2000);
+      return new completion.FuzzyHistoryCompleter(8000);
     else if (name === 'bookmarks')
       return new completion.FuzzyBookmarkCompleter();
     else if (name === 'tabs')
-- 
cgit v1.2.3


From 0ab64a092def03ccd462802f040d83ce2911ea1e Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 25 Jan 2012 22:32:08 +0100
Subject: really only update every X milliseconds

---
 fuzzyMode.js | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index a2ff7dc5..2a9b4601 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -75,8 +75,7 @@ var fuzzyMode = (function() {
 
     reset: function() {
       this.query = '';
-      // query used to filter the last completion result. We need this for asynchronous updating
-      this.lastQuery = null;
+      this.updateTimer = null;
       this.completions = [];
       this.selection = 0;
       // force synchronous updating so that the old results will not be flash up shortly
@@ -121,8 +120,7 @@ var fuzzyMode = (function() {
       // refresh with F5
       else if (keyChar == 'f5') {
         this.completer.refresh();
-        this.lastQuery = null;
-        this.update();
+        this.update(true); // force synchronous update
       }
 
       // use primary action with Enter. Holding down Shift/Ctrl uses the alternative action
@@ -150,6 +148,7 @@ var fuzzyMode = (function() {
 
     updateCompletions: function() {
       var self = this;
+      var start = Date.now();
       this.completer.filter(this.query, this.maxResults, function(completions) {
         self.completions = completions;
 
@@ -157,6 +156,7 @@ var fuzzyMode = (function() {
         self.completionList.innerHTML = completions.map(function(completion) {
           return '<li>' + completion.html + '</li>';
         }).join('');
+        console.log("total update time: " + (Date.now() - start));
 
         self.completionList.style.display = self.completions.length > 0 ? 'block' : 'none';
         self.updateSelection();
@@ -170,16 +170,20 @@ var fuzzyMode = (function() {
       this.input.textContent = this.query;
 
       if (sync) {
+        // cancel scheduled update
+        if (this.updateTimer !== null)
+          window.clearTimeout(this.updateTimer);
         this.updateCompletions();
+      } else if (this.updateTimer !== null) {
+        // an update is already scheduled, don't do anything
+        return;
       } else {
         var self = this;
         // always update asynchronously for better user experience and to take some load off the CPU
         // (not every keystroke will cause a dedicated update)
-        setTimeout(function() {
-          if (self.query === self.lastQuery)
-            return;
-          self.lastQuery = self.query;
+        this.updateTimer = setTimeout(function() {
           self.updateCompletions();
+          self.updateTimer = null;
         }, this.refreshInterval);
       }
     },
@@ -201,8 +205,8 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activateAll:       function() { start('all',        false, 300); },
-    activateAllNewTab: function() { start('all',        true,  300);  },
+    activateAll:       function() { start('all',        false, 100); },
+    activateAllNewTab: function() { start('all',        true,  100);  },
     activateTabs:      function() { start('tabsSorted', false, 0); },
   }
 
-- 
cgit v1.2.3


From 3449af0461782c24c8577fe4a5938f35f417cbb1 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 19:21:54 +0100
Subject: move completion logic to background page

This has the following advantages:
* searching is done in the background, UI responsiveness is improved
* caches are no longer duplicated. This saves RAM and improves performance
---
 background_page.html |  94 ++++++++----------------
 fuzzyMode.js         |  75 +++++++------------
 lib/completion.js    | 204 +++++++++++++++++++++++++++++++++------------------
 3 files changed, 189 insertions(+), 184 deletions(-)

diff --git a/background_page.html b/background_page.html
index a56028bc..f760ea70 100644
--- a/background_page.html
+++ b/background_page.html
@@ -4,6 +4,7 @@
 <script type="text/javascript" src="lib/clipboard.js"></script>
 <script type="text/javascript" src="lib/utils.js"></script>
 <script type="text/javascript" src="background/settings.js"></script>
+<script type="text/javascript" src="lib/completion.js"></script>
 <script type="text/javascript" charset="utf-8">
   var currentVersion = utils.getCurrentVersion();
 
@@ -27,9 +28,7 @@
     getCurrentTabUrl:     getCurrentTabUrl,
     settings:             handleSettings,
     getBookmarks:         getBookmarks,
-    getAllBookmarks:      getAllBookmarks,
-    getHistory:           getHistory,
-    getTabsInCurrentWindow: getTabsInCurrentWindow,
+    filterCompleter:      filterCompleter,
   };
 
   var sendRequestHandlers = {
@@ -46,6 +45,7 @@
     isEnabledForUrl: isEnabledForUrl,
     saveHelpDialogSettings: saveHelpDialogSettings,
     selectSpecificTab: selectSpecificTab,
+    refreshCompleter: refreshCompleter,
   };
 
   // Event handlers
@@ -53,6 +53,28 @@
   var getScrollPositionHandlers = {}; // tabId -> function(tab, scrollX, scrollY);
   var tabLoadedHandlers = {}; // tabId -> function()
 
+  var completionSources = {
+    smart:     new completion.SmartCompletionSource({
+      'wiki ': [ 'Wikipedia (en)',    'http://en.wikipedia.org/wiki/%s' ],
+      'luck ': [ 'Google Lucky (en)', 'http://www.google.com/search?q=%s&btnI=I%27m+Feeling+Lucky' ],
+      'cc '  : [ 'dict.cc',           'http://www.dict.cc/?s=%s' ],
+      ';'    : [ 'goto',              '%s' ],
+      '?'    : [ 'search',            function(query) { return utils.createSearchUrl(query) } ],
+      }),
+    bookmarks: new completion.FuzzyBookmarkCompletionSource(),
+    history:   new completion.FuzzyHistoryCompletionSource(20000),
+    tabs:      new completion.FuzzyTabCompletionSource(),
+  }
+  var completers = {
+    omni: new completion.MultiCompleter([
+                  completionSources.smart,
+                  completionSources.bookmarks,
+                  completionSources.history,
+                  completionSources.tabs,
+                  ], 1),
+    tabs: new completion.MultiCompleter([ completionSources.tabs ], 0),
+  };
+
   chrome.extension.onConnect.addListener(function(port, name) {
     var senderTabId = port.sender.tab ? port.sender.tab.id : null;
     // If this is a tab we've been waiting to open, execute any "tab loaded" handlers, e.g. to restore
@@ -74,9 +96,6 @@
 
     if (portHandlers[port.name])
       port.onMessage.addListener(portHandlers[port.name]);
-
-    // prefetch history
-    useHistory(function() {});
   });
 
   chrome.extension.onRequest.addListener(function (request, sender, sendResponse) {
@@ -289,66 +308,15 @@
     })
   }
 
-  function getAllBookmarks(args, port) {
-    function traverseTree(bookmarks, callback) {
-      for (var i = 0; i < bookmarks.length; ++i) {
-        callback(bookmarks[i]);
-        if (typeof bookmarks[i].children === "undefined")
-          continue;
-        traverseTree(bookmarks[i].children, callback);
-      }
-    };
-
-    chrome.bookmarks.getTree(function(bookmarks) {
-      var results = [];
-      traverseTree(bookmarks, function(bookmark) {
-        results.push(bookmark);
-      });
-      port.postMessage({bookmarks:results});
-    });
-  };
-
-  var cachedHistory = null;
-  function useHistory(callback) {
-    if (cachedHistory !== null) {
-      callback(cachedHistory);
-      return;
-    }
-
-    chrome.history.search({
-        text: '',
-        maxResults: 20000,
-        startTime: 0,
-    }, function(history) {
-      // sorting in ascending order, so we can push new items to the end later
-      history.sort(function(a, b) {
-        return (a.lastVisitTime|| 0) - (b.lastVisitTime || 0);
-      });
-      cachedHistory = history;
-      callback(cachedHistory);
-    });
+  function refreshCompleter(request) {
+    completers[request.name].refresh();
   }
 
-  chrome.history.onVisited.addListener(function(item) {
-    if (cachedHistory === null) return;
-    // only cache newly visited sites
-    if (item.visitCount === 1)
-      cachedHistory.push(item);
-  });
-
-  function getHistory(args, port) {
-    useHistory(function(history) {
-      port.postMessage({
-        history: history.slice(Math.max(history.length - args.maxResults, 0))
-      });
+  function filterCompleter(args, port) {
+    completers[args.name].filter(args.query, args.maxResults, function(results) {
+      port.postMessage({ id: args.id, results: results });
     });
-  };
-
-  function getTabsInCurrentWindow(args, port) {
-    chrome.tabs.getAllInWindow(null, function(tabs) {
-      port.postMessage({tabs:tabs});
-    });
-  };
+  }
 
   /*
    * Used by everyone to get settings from local storage.
diff --git a/fuzzyMode.js b/fuzzyMode.js
index 2a9b4601..8dbad5cc 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -1,35 +1,10 @@
 var fuzzyMode = (function() {
   var fuzzyBox = null;  // the dialog instance for this window
-  var completers = {};  // completer cache
-
-  function createCompleter(name) {
-    if (name === 'smart')
-      return new completion.SmartCompleter({
-        'wiki ': [ 'Wikipedia (en)', 'http://en.wikipedia.org/wiki/%s' ],
-        'luck ': [ 'Google Lucky (en)', 'http://www.google.com/search?q=%s&btnI=I%27m+Feeling+Lucky' ],
-        'cc '  : [ 'dict.cc',        'http://www.dict.cc/?s=%s' ],
-        ';'    : [ 'goto',           '%s' ],
-        '?'    : [ 'search',         function(query) { return utils.createSearchUrl(query) } ],
-        });
-    else if (name === 'history')
-      return new completion.FuzzyHistoryCompleter(8000);
-    else if (name === 'bookmarks')
-      return new completion.FuzzyBookmarkCompleter();
-    else if (name === 'tabs')
-      return new completion.FuzzyTabCompleter();
-    else if (name === 'tabsSorted')
-      return new completion.MergingCompleter([getCompleter('tabs')], 0);
-    else if (name === 'all')
-      return new completion.MergingCompleter([
-        getCompleter('smart'),
-        getCompleter('bookmarks'),
-        getCompleter('history'),
-        getCompleter('tabs'),
-        ], 1);
-  }
+  var completers = { };
+
   function getCompleter(name) {
     if (!(name in completers))
-      completers[name] = createCompleter(name);
+      completers[name] = new completion.BackgroundCompleter(name);
     return completers[name];
   }
 
@@ -70,6 +45,7 @@ var fuzzyMode = (function() {
 
     hide: function() {
       this.box.style.display = 'none';
+      this.completionList.style.display = 'none';
       handlerStack.pop();
     },
 
@@ -78,7 +54,6 @@ var fuzzyMode = (function() {
       this.updateTimer = null;
       this.completions = [];
       this.selection = 0;
-      // force synchronous updating so that the old results will not be flash up shortly
       this.update(true);
     },
 
@@ -90,6 +65,7 @@ var fuzzyMode = (function() {
     },
 
     onKeydown: function(event) {
+      var self = this;
       var keyChar = getKeyChar(event);
 
       if (isEscape(event)) {
@@ -120,20 +96,19 @@ var fuzzyMode = (function() {
       // refresh with F5
       else if (keyChar == 'f5') {
         this.completer.refresh();
-        this.update(true); // force synchronous update
+        this.update(true); // force immediate update
       }
 
       // use primary action with Enter. Holding down Shift/Ctrl uses the alternative action
       // (opening in new tab)
       else if (event.keyCode == keyCodes.enter) {
-        this.update(true); // force synchronous update
-
-        var alternative = (event.shiftKey || isPrimaryModifierKey(event));
-        if (this.reverseAction)
-          alternative = !alternative;
-        this.completions[this.selection].action[alternative ? 1 : 0]();
-        this.hide();
-        this.reset();
+        this.update(true, function() {
+          var alternative = (event.shiftKey || isPrimaryModifierKey(event));
+          if (self.reverseAction)
+            alternative = !alternative;
+          self.completions[self.selection].action[alternative ? 1 : 0]();
+          self.hide();
+        });
       }
 
       else if (keyChar.length == 1) {
@@ -146,34 +121,34 @@ var fuzzyMode = (function() {
       return true;
     },
 
-    updateCompletions: function() {
+    updateCompletions: function(callback) {
       var self = this;
-      var start = Date.now();
+      //var start = Date.now();
       this.completer.filter(this.query, this.maxResults, function(completions) {
         self.completions = completions;
 
-        // clear completions
+        // update completion list with the new data
         self.completionList.innerHTML = completions.map(function(completion) {
           return '<li>' + completion.html + '</li>';
         }).join('');
-        console.log("total update time: " + (Date.now() - start));
 
         self.completionList.style.display = self.completions.length > 0 ? 'block' : 'none';
         self.updateSelection();
+        if (callback) callback();
       });
     },
 
-    update: function(sync) {
-      sync = sync || false; // explicitely default to asynchronous updating
+    update: function(force, callback) {
+      force = force || false; // explicitely default to asynchronous updating
 
       this.query = this.query.replace(/^\s*/, '');
       this.input.textContent = this.query;
 
-      if (sync) {
+      if (force) {
         // cancel scheduled update
         if (this.updateTimer !== null)
           window.clearTimeout(this.updateTimer);
-        this.updateCompletions();
+        this.updateCompletions(callback);
       } else if (this.updateTimer !== null) {
         // an update is already scheduled, don't do anything
         return;
@@ -182,7 +157,7 @@ var fuzzyMode = (function() {
         // always update asynchronously for better user experience and to take some load off the CPU
         // (not every keystroke will cause a dedicated update)
         this.updateTimer = setTimeout(function() {
-          self.updateCompletions();
+          self.updateCompletions(callback);
           self.updateTimer = null;
         }, this.refreshInterval);
       }
@@ -205,9 +180,9 @@ var fuzzyMode = (function() {
 
   // public interface
   return {
-    activateAll:       function() { start('all',        false, 100); },
-    activateAllNewTab: function() { start('all',        true,  100);  },
-    activateTabs:      function() { start('tabsSorted', false, 0); },
+    activateAll:       function() { start('omni', false, 200); },
+    activateAllNewTab: function() { start('omni', true,  200);  },
+    activateTabs:      function() { start('tabs', false,  200);  },
   }
 
 })();
diff --git a/lib/completion.js b/lib/completion.js
index 1915a83a..f04eb356 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -195,6 +195,14 @@ var completion = (function() {
       return [ open(false), open(true, true), open(true, false) ];
   }
 
+  /** Returns an action that switches to the tab with the given :id. */
+  function createActionSwitchToTab(id) {
+    var open = function() {
+      chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: id });
+    }
+    return [open, open, open];
+  }
+
   /** Creates an file-internal representation of a URL match with the given paramters */
   function createCompletionHtml(type, str, title) {
     title = title || '';
@@ -259,32 +267,17 @@ var completion = (function() {
 
   /** Helper class to construct fuzzy completers for asynchronous data sources like history or bookmark
    * matchers. */
-  var AsyncCompleter = function() {
-    this.completions = null;
+  var AsyncCompletionSource = function() {
     this.id = utils.createUniqueId();
-    this.readyCallback = this.fallbackReadyCallback = function(results) {
+    this.reset();
+    this.resultsReady = this.fallbackReadyCallback = function(results) {
       this.completions = results;
     }
   }
-  AsyncCompleter.prototype = {
-    /** Convenience function to remove shared code in the completers. Clears the completion cache, sends
-     * a message to an extension port and pipes the returned message through a callback before storing it into
-     * the instance's completion cache.
-     */
-    fetchFromPort: function(name, query, callback) {
-      this.completions = null; // reset completions
-
-      // asynchronously fetch from a port
-      var port = chrome.extension.connect({ name: name }) ;
-      var self = this;
-      port.onMessage.addListener(function(msg) {
-        self.readyCallback(callback(msg));
-      });
-      port.postMessage(query);
-    },
-
-    resetCache: function() {
+  AsyncCompletionSource.prototype = {
+    reset: function() {
       fuzzyMatcher.invalidateFilterCache(this.id);
+      this.completions = null;
     },
 
     /** Convenience function to remove shared code in the completers. Creates an internal representation of
@@ -294,7 +287,7 @@ var completion = (function() {
       var url = item.url;
       var parts = [type, url, item.title];
       var str = parts.join(' ');
-      action = action || createActionOpenUrl(url);
+      action = action || {func: 'completion.createActionOpenUrl', args: [url]};
 
       function createLazyCompletion(query) {
         return new LazyCompletion(url.length / fuzzyMatcher.calculateRelevancy(query, str), function() {
@@ -333,10 +326,10 @@ var completion = (function() {
         handler(this.completions);
       } else {
         // no: register the handler as a callback
-        this.readyCallback = function(results) {
+        this.resultsReady = function(results) {
           handler(results);
-          self.readyCallback = self.fallbackReadyCallback;
-          self.readyCallback(results);
+          self.resultsReady = self.fallbackReadyCallback;
+          self.resultsReady(results);
         }
       }
     },
@@ -346,7 +339,7 @@ var completion = (function() {
 
   /** A simple completer that suggests to open the input string as an URL or to trigger a web search for the
    * given term, depending on whether it thinks the input is an URL or not. */
-  var SmartCompleter = function(commands) {
+  var SmartCompletionSource = function(commands) {
     commands = commands || {};
     var commandKeys = Object.keys(commands);
 
@@ -364,7 +357,7 @@ var completion = (function() {
         return new LazyCompletion(-2, function() {
           return {
             html:   createCompletionHtml(desc, term),
-            action: createActionOpenUrl(utils.createFullUrl(url)),
+            action: {func: 'completion.createActionOpenUrl', args: [utils.createFullUrl(url)]},
           }})
       });
     }
@@ -379,8 +372,8 @@ var completion = (function() {
       return new LazyCompletion(-1, function() {
         return {
           html: createCompletionHtml(isUrl ? 'goto' : 'search', query),
-          action: createActionOpenUrl(isUrl ? utils.createFullUrl(query)
-                                            : utils.createSearchUrl(query)),
+          action: {func: 'completion.createActionOpenUrl', args: isUrl ? [utils.createFullUrl(query)]
+                                                                       : [utils.createSearchUrl(query)]},
         }});
     }
 
@@ -391,69 +384,134 @@ var completion = (function() {
     }
   }
 
-  /** A fuzzy history completer */
-  var FuzzyHistoryCompleter = function(maxResults) {
-    AsyncCompleter.call(this);
-    this.maxResults = maxResults || 1000;
+  /** A fuzzy bookmark completer */
+  var FuzzyBookmarkCompletionSource = function() {
+    AsyncCompletionSource.call(this);
   }
-  utils.extend(AsyncCompleter, FuzzyHistoryCompleter);
+  utils.extend(AsyncCompletionSource, FuzzyBookmarkCompletionSource);
 
-  FuzzyHistoryCompleter.prototype.refresh = function() {
+  FuzzyBookmarkCompletionSource.prototype.traverseTree = function(bookmarks, results) {
     var self = this;
-    self.resetCache();
-    self.fetchFromPort('getHistory', { maxResults: self.maxResults }, function(msg) {
-      return msg.history.map(function(item) {
-        return self.createInternalMatch('history', item);
-      });
+    bookmarks.forEach(function(bookmark) {
+      results.push(bookmark);
+      if (bookmark.children === undefined)
+        return;
+      self.traverseTree(bookmark.children, results);
     });
   }
 
-  /** A fuzzy bookmark completer */
-  var FuzzyBookmarkCompleter = function() {
-    AsyncCompleter.call(this);
+  FuzzyBookmarkCompletionSource.prototype.refresh = function() {
+    var self = this; self.reset();
+    chrome.bookmarks.getTree(function(bookmarks) {
+      var results = [];
+      self.traverseTree(bookmarks, results);
+
+      self.resultsReady(results.filter(function(b) { return b.url !== undefined; })
+                              .map(function(bookmark) {
+        return self.createInternalMatch('bookmark', bookmark);
+      }));
+    });
+  }
+
+  /** A fuzzy history completer */
+  var FuzzyHistoryCompletionSource = function(maxResults) {
+    AsyncCompletionSource.call(this);
+    this.cachedHistory = null;
+    this.maxResults = maxResults;
   }
-  utils.extend(AsyncCompleter, FuzzyBookmarkCompleter);
+  utils.extend(AsyncCompletionSource, FuzzyHistoryCompletionSource);
 
-  FuzzyBookmarkCompleter.prototype.refresh = function() {
+  FuzzyHistoryCompletionSource.prototype.useHistory = function(callback) {
     var self = this;
-    self.resetCache();
-    self.fetchFromPort('getAllBookmarks', {}, function(msg) {
-      return msg.bookmarks.filter(function(bookmark) { return bookmark.url !== undefined })
-                          .map(function(bookmark) {
-        return self.createInternalMatch('bookmark', bookmark);
+    if (self.cachedHistory !== null)
+      return callback(self.cachedHistory);
+
+    chrome.history.search({
+        text: '',
+        maxResults: 20000,
+        startTime: 0,
+    }, function(history) {
+      // sorting in ascending order, so we can push new items to the end later
+      history.sort(function(a, b) {
+        return (a.lastVisitTime|| 0) - (b.lastVisitTime || 0);
       });
+      self.cachedHistory = history;
+      callback(history);
+    });
+
+    chrome.history.onVisited.addListener(function(item) {
+      // only cache newly visited sites
+      if (item.visitCount === 1)
+        self.cachedHistory.push(item);
+    });
+  }
+
+  FuzzyHistoryCompletionSource.prototype.refresh = function() {
+    var self = this;
+    self.reset();
+
+    self.useHistory(function(history) {
+      self.resultsReady(history.slice(-self.maxResults).map(function(item) {
+        return self.createInternalMatch('history', item);
+      }))
     });
   }
 
   /** A fuzzy tab completer */
-  var FuzzyTabCompleter = function() {
-    AsyncCompleter.call(this);
+  var FuzzyTabCompletionSource = function() {
+    AsyncCompletionSource.call(this);
   }
-  utils.extend(AsyncCompleter, FuzzyTabCompleter);
+  utils.extend(AsyncCompletionSource, FuzzyTabCompletionSource);
 
-  FuzzyTabCompleter.prototype.refresh = function() {
+  FuzzyTabCompletionSource.prototype.refresh = function() {
     var self = this;
-    self.resetCache();
-    self.fetchFromPort('getTabsInCurrentWindow', {}, function(msg) {
-      return msg.tabs.map(function(tab) {
-        var open = function() {
-          chrome.extension.sendRequest({ handler: 'selectSpecificTab', id: tab.id });
-        }
-        return self.createInternalMatch('tab', tab, [open, open, open]);
-      });
+    self.reset();
+
+    chrome.tabs.getAllInWindow(null, function(tabs) {
+      self.resultsReady(tabs.map(function(tab) {
+        return self.createInternalMatch('tab', tab,
+                                        { func: 'completion.createActionSwitchToTab',
+                                          args: [tab.id] });
+      }));
     });
   }
 
+  var BackgroundCompleter = function(name) {
+    this.name = name;
+    this.filterPort = chrome.extension.connect({ name: 'filterCompleter' });
+  }
+  BackgroundCompleter.prototype = {
+    refresh: function() {
+      chrome.extension.sendRequest({ handler: 'refreshCompleter', name: this.name });
+    },
+
+    filter: function(query, maxResults, callback) {
+      var id = utils.createUniqueId();
+      this.filterPort.onMessage.addListener(function(msg) {
+        if (msg.id != id) return;
+        callback(msg.results.map(function(result) {
+          var action = result.action;
+          result.action = eval(action.func).apply(null, action.args);
+          return result;
+        }));
+      });
+      this.filterPort.postMessage({ id: id,
+                                    name: this.name,
+                                    query: query,
+                                    maxResults: maxResults });
+    },
+  }
+
   /** A meta-completer that delegates queries and merges and sorts the results of a collection of other
    * completer instances given in :sources. The optional argument :queryThreshold determines how long a
-   * query has to be to trigger a refresh. */
-  var MergingCompleter = function(sources, queryThreshold) {
+   * query has to be to trigger a search. */
+  var MultiCompleter = function(sources, queryThreshold) {
     if (queryThreshold === undefined)
       queryThreshold = 1; // default
     this.sources = sources;
     this.queryThreshold = queryThreshold;
   }
-  MergingCompleter.prototype = {
+  MultiCompleter.prototype = {
     refresh: function() {
       this.sources.forEach(function(x) { x.refresh(); });
     },
@@ -464,6 +522,7 @@ var completion = (function() {
         return;
       }
 
+      var self = this;
       var all = [];
       var counter = this.sources.length;
 
@@ -484,10 +543,13 @@ var completion = (function() {
 
   // public interface
   return {
-    FuzzyHistoryCompleter: FuzzyHistoryCompleter,
-    FuzzyBookmarkCompleter: FuzzyBookmarkCompleter,
-    FuzzyTabCompleter: FuzzyTabCompleter,
-    SmartCompleter: SmartCompleter,
-    MergingCompleter: MergingCompleter,
+    FuzzyBookmarkCompletionSource: FuzzyBookmarkCompletionSource,
+    FuzzyHistoryCompletionSource: FuzzyHistoryCompletionSource,
+    FuzzyTabCompletionSource: FuzzyTabCompletionSource,
+    SmartCompletionSource: SmartCompletionSource,
+    MultiCompleter: MultiCompleter,
+    BackgroundCompleter: BackgroundCompleter,
+    createActionOpenUrl: createActionOpenUrl,
+    createActionSwitchToTab: createActionSwitchToTab,
   };
-})();
+})()
-- 
cgit v1.2.3


From bcc0e029fdce32ca4c3d494b00f0a08eb3195e06 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 19:27:00 +0100
Subject: small tweaks

---
 fuzzyMode.js | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index 8dbad5cc..aab89e16 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -175,14 +175,15 @@ var fuzzyMode = (function() {
 
       this.input          = document.querySelector("#fuzzybox .query");
       this.completionList = document.querySelector("#fuzzybox ul");
+      this.completionList.style.display = 'none';
     },
   }
 
   // public interface
   return {
-    activateAll:       function() { start('omni', false, 200); },
-    activateAllNewTab: function() { start('omni', true,  200);  },
-    activateTabs:      function() { start('tabs', false,  200);  },
+    activateAll:       function() { start('omni', false, 100); },
+    activateAllNewTab: function() { start('omni', true,  100);  },
+    activateTabs:      function() { start('tabs', false, 0);  },
   }
 
 })();
-- 
cgit v1.2.3


From 7eb205f7d45b72d793d9109848293555ba21ed51 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 19:57:56 +0100
Subject: optimization

---
 lib/completion.js | 44 +++++++++++++++++++++++++++++---------------
 1 file changed, 29 insertions(+), 15 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index f04eb356..b3e70516 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -7,18 +7,21 @@ var completion = (function() {
     var self = {};
 
     self.timeToClean = 0;
-    self.matcherCacheSize = 300;
+    self.cacheSize = 1000;
     self.regexNonWord = /[\W_]/ig;
 
     // cache generated regular expressions
     self.matcherCache = {};
     // cache filtered results from recent queries
     self.filterCache = {};
+    self.normalizationCache = {};
 
     /** Normalizes the string specified in :query. Strips any non-word characters and converts
      * to lower case. */
     self.normalize = function(query) {
-      return query.replace(self.regexNonWord, '').toLowerCase();
+      if (!(query in self.normalizationCache))
+        self.normalizationCache[query] = query.replace(self.regexNonWord, '').toLowerCase();
+      return self.normalizationCache[query];
     }
 
     /** Returns the non-matching and matching string parts, in alternating order (starting with a
@@ -80,12 +83,17 @@ var completion = (function() {
       return sum * sum * sum;
     }
 
-    /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
-    self.cleanMatcherCache = function() {
-      // remove old matchers
-      Object.keys(self.matcherCache).forEach(function(query) {
+    /** Trims the size of the caches to the configured size using a FIFO algorithm. */
+    self.cleanCache = function() {
+      console.log("cleaning cache");
+      // remove old cached regexes
+      Object.keys(self.matcherCache).slice(self.cacheSize).forEach(function(query) {
         delete self.matcherCache[query];
       });
+      // remove old cached normalization results
+      Object.keys(self.normalizationCache).slice(self.cacheSize).forEach(function(query) {
+        delete self.normalizationCache[query];
+      });
     }
 
     /** Returns a regex that matches a string using a fuzzy :query. Example: The :query "abc" would result
@@ -94,12 +102,18 @@ var completion = (function() {
     self.getMatcher = function(query) {
       query = self.normalize(query);
       if (!(query in self.matcherCache)) {
-        // build up a regex for fuzzy matching
-        // TODO use an array and .join here
-        var regex = '^';
-        for (var i = 0; i < query.length; ++i)
-          regex += '([^' + query[i] + ']*)(' + query[i] + ')';
-        self.matcherCache[query] = new RegExp(regex + '(.*)$', 'i');
+        // build up a regex for fuzzy matching. This is the fastest method I checked (faster than:
+        // string building, splice, concat, multi-level join)
+        var regex = ['^'];
+        for (var i = 0; i < query.length; ++i) {
+          regex.push('([^');
+          regex.push(query[i]);
+          regex.push(']*)(');
+          regex.push(query[i]);
+          regex.push(')');
+        }
+        regex.push('(.*)$');
+        self.matcherCache[query] = new RegExp(regex.join(''), 'i');
       }
       return self.matcherCache[query];
     }
@@ -142,10 +156,10 @@ var completion = (function() {
         }
       }
 
-      // don't clean up the cache every iteration
-      if (++self.timeToClean > 20) {
+      // don't clean up the caches every iteration
+      if (++self.timeToClean > 100) {
         self.timeToClean = 0;
-        self.cleanMatcherCache();
+        self.cleanCache();
       }
 
       var matcher = self.getMatcher(query);
-- 
cgit v1.2.3


From f28edd6bcb2a84e7c36700af102006c95468a265 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 21:45:01 +0100
Subject: small changes

---
 lib/completion.js | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index b3e70516..58f140f9 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -63,19 +63,18 @@ var completion = (function() {
       return null;
     }
 
-    /** Calculates a very simple similarity value between a :query and a :string. The current
-     * implementation simply returns the cumulated length of query parts that are also found
-     * in the string, raised to the power of 3.
-     */
+    /** Calculates a very simple similarity value between a :query and a :string */
     self.calculateRelevancy = function(query, str) {
       query = self.normalize(query);
       str   = self.normalize(str);
       var sum = 0;
+
       // only iterate over slices of the query starting at an offset up to 10 to save resources
       for (var start = 0; start < 20 && start < query.length; ++start) {
         for (var i = query.length; i >= start; --i) {
           if (str.indexOf(query.slice(start, i)) >= 0) {
-            sum += (i - start) * (i - start);
+            var length = i - start;
+            sum += length * length;
             break;
           }
         }
@@ -173,7 +172,7 @@ var completion = (function() {
 
   var htmlRegex = /<[^>]*>|&[a-z]+;/gi;
 
-  /** Strips HTML tags and escape sequences using a naive regex replacement. Optionally, saves the stripped
+  /** Strips HTML tags and entities using a naive regex replacement. Optionally, saves the stripped
    * HTML tags in a dictionary indexed by the position where the tag should be reinserted. */
   function stripHtmlTags(str, positions) {
     if (!positions)
-- 
cgit v1.2.3


From 5ee53fc3ef8d4b3a2a616843accb77c30849a26f Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 23:02:57 +0100
Subject: add domain completion a la Chrome omnibox

---
 background_page.html |   2 +
 lib/completion.js    | 117 ++++++++++++++++++++++++++++++++++++++-------------
 2 files changed, 90 insertions(+), 29 deletions(-)

diff --git a/background_page.html b/background_page.html
index f760ea70..6476b474 100644
--- a/background_page.html
+++ b/background_page.html
@@ -61,12 +61,14 @@
       ';'    : [ 'goto',              '%s' ],
       '?'    : [ 'search',            function(query) { return utils.createSearchUrl(query) } ],
       }),
+    domain:    new completion.DomainCompletionSource(),
     bookmarks: new completion.FuzzyBookmarkCompletionSource(),
     history:   new completion.FuzzyHistoryCompletionSource(20000),
     tabs:      new completion.FuzzyTabCompletionSource(),
   }
   var completers = {
     omni: new completion.MultiCompleter([
+                  completionSources.domain,
                   completionSources.smart,
                   completionSources.bookmarks,
                   completionSources.history,
diff --git a/lib/completion.js b/lib/completion.js
index 58f140f9..935773a5 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -84,7 +84,6 @@ var completion = (function() {
 
     /** Trims the size of the caches to the configured size using a FIFO algorithm. */
     self.cleanCache = function() {
-      console.log("cleaning cache");
       // remove old cached regexes
       Object.keys(self.matcherCache).slice(self.cacheSize).forEach(function(query) {
         delete self.matcherCache[query];
@@ -178,7 +177,9 @@ var completion = (function() {
     if (!positions)
       return str.replace(htmlRegex, '');
 
-    var match = str.match(htmlRegex).reverse();
+    var match = str.match(htmlRegex);
+    if (!match) return;
+    match.reverse();
     var split = str.split(htmlRegex);
     var offset = 0;
     var i = 0;
@@ -278,6 +279,34 @@ var completion = (function() {
     this.build = builder;
   }
 
+  /** Singleton object that provides fast access to the Chrome history */
+  var historyCache = (function() {
+    var size = 20000;
+    var cachedHistory = null;
+
+    function use(callback) {
+      if (cachedHistory !== null)
+        return callback(cachedHistory);
+
+      chrome.history.search({ text: '', maxResults: size, startTime: 0 }, function(history) {
+        // sorting in ascending order, so we can push new items to the end later
+        history.sort(function(a, b) {
+          return (a.lastVisitTime|| 0) - (b.lastVisitTime || 0);
+        });
+        cachedHistory = history;
+        callback(history);
+      });
+
+      chrome.history.onVisited.addListener(function(item) {
+        // only cache newly visited sites
+        if (item.visitCount === 1)
+          cachedHistory.push(item);
+      });
+    }
+
+    return { use: use };
+  })()
+
   /** Helper class to construct fuzzy completers for asynchronous data sources like history or bookmark
    * matchers. */
   var AsyncCompletionSource = function() {
@@ -429,41 +458,15 @@ var completion = (function() {
   /** A fuzzy history completer */
   var FuzzyHistoryCompletionSource = function(maxResults) {
     AsyncCompletionSource.call(this);
-    this.cachedHistory = null;
     this.maxResults = maxResults;
   }
   utils.extend(AsyncCompletionSource, FuzzyHistoryCompletionSource);
 
-  FuzzyHistoryCompletionSource.prototype.useHistory = function(callback) {
-    var self = this;
-    if (self.cachedHistory !== null)
-      return callback(self.cachedHistory);
-
-    chrome.history.search({
-        text: '',
-        maxResults: 20000,
-        startTime: 0,
-    }, function(history) {
-      // sorting in ascending order, so we can push new items to the end later
-      history.sort(function(a, b) {
-        return (a.lastVisitTime|| 0) - (b.lastVisitTime || 0);
-      });
-      self.cachedHistory = history;
-      callback(history);
-    });
-
-    chrome.history.onVisited.addListener(function(item) {
-      // only cache newly visited sites
-      if (item.visitCount === 1)
-        self.cachedHistory.push(item);
-    });
-  }
-
   FuzzyHistoryCompletionSource.prototype.refresh = function() {
     var self = this;
     self.reset();
 
-    self.useHistory(function(history) {
+    historyCache.use(function(history) {
       self.resultsReady(history.slice(-self.maxResults).map(function(item) {
         return self.createInternalMatch('history', item);
       }))
@@ -489,6 +492,61 @@ var completion = (function() {
     });
   }
 
+  /** A domain completer as it is provided by Chrome's omnibox */
+  var DomainCompletionSource = function() {
+    this.domains = null;
+  }
+
+  DomainCompletionSource.prototype.withDomains = function(callback) {
+    var self = this;
+    if (self.domains !== null)
+      return callback(Object.keys(self.domains));
+
+    self.domains = {};
+
+    function processDomain(domain) {
+      self.domains[domain] = true;
+      delete self.domains['www.' + domain];
+    }
+    function extractDomain(url) { return url.split('/')[2]; }
+
+    historyCache.use(function(history) {
+      history.forEach(function(item) {
+        processDomain(extractDomain(item.url));
+      });
+    });
+    // delete redundant www. domains
+    Object.keys(self.domains).forEach(function(domain) { processDomain(domain); });
+
+    chrome.history.onVisited.addListener(function(item) {
+      processDomain(extractDomain(item.url));
+    });
+    callback(Object.keys(self.domains));
+  }
+
+  DomainCompletionSource.prototype.refresh = function() { }
+  DomainCompletionSource.prototype.filter = function(query, callback) {
+    var best = null;
+    this.withDomains(function(domains) {
+      var bestOffset = 1000;
+      domains.forEach(function(domain) {
+        var offset = domain.indexOf(query);
+        if (offset < 0 || offset >= bestOffset)
+          return;
+
+        // found a new optimum
+        bestOffset = offset;
+        best = new LazyCompletion(-1.5, function() {
+          return {
+            html:   createCompletionHtml('site', domain),
+            action: {func: 'completion.createActionOpenUrl', args: [utils.createFullUrl(domain)]},
+          }});
+      });
+    });
+    callback(best ? [best] : []);
+  }
+
+  /** Get completion results from the background page */
   var BackgroundCompleter = function(name) {
     this.name = name;
     this.filterPort = chrome.extension.connect({ name: 'filterCompleter' });
@@ -560,6 +618,7 @@ var completion = (function() {
     FuzzyHistoryCompletionSource: FuzzyHistoryCompletionSource,
     FuzzyTabCompletionSource: FuzzyTabCompletionSource,
     SmartCompletionSource: SmartCompletionSource,
+    DomainCompletionSource: DomainCompletionSource,
     MultiCompleter: MultiCompleter,
     BackgroundCompleter: BackgroundCompleter,
     createActionOpenUrl: createActionOpenUrl,
-- 
cgit v1.2.3


From b56ee2730cd78f522ae62800ae5fbe53e43b096e Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 27 Jan 2012 23:04:37 +0100
Subject: don't complete tabs in omni mode

---
 background_page.html | 1 -
 1 file changed, 1 deletion(-)

diff --git a/background_page.html b/background_page.html
index 6476b474..9ce9fe22 100644
--- a/background_page.html
+++ b/background_page.html
@@ -72,7 +72,6 @@
                   completionSources.smart,
                   completionSources.bookmarks,
                   completionSources.history,
-                  completionSources.tabs,
                   ], 1),
     tabs: new completion.MultiCompleter([ completionSources.tabs ], 0),
   };
-- 
cgit v1.2.3


From 09aaab6967881b22431d3e4eaafdac14865fdda0 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 11 Apr 2012 00:03:40 +0200
Subject: fix strange whitespace artefacts

---
 lib/completion.js | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 935773a5..8b63fab0 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -103,14 +103,14 @@ var completion = (function() {
         // build up a regex for fuzzy matching. This is the fastest method I checked (faster than:
         // string building, splice, concat, multi-level join)
         var regex = ['^'];
-        for (var i = 0; i < query.length; ++i) {
-          regex.push('([^');
-          regex.push(query[i]);
-          regex.push(']*)(');
-          regex.push(query[i]);
-          regex.push(')');
-        }
-        regex.push('(.*)$');
+        for (var i = 0; i < query.length; ++i) {
+          regex.push('([^');
+          regex.push(query[i]);
+          regex.push(']*)(');
+          regex.push(query[i]);
+          regex.push(')');
+        }
+        regex.push('(.*)$');
         self.matcherCache[query] = new RegExp(regex.join(''), 'i');
       }
       return self.matcherCache[query];
-- 
cgit v1.2.3


From bb37bcc35c2f027242737fcabb17d51c699710a9 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Wed, 11 Apr 2012 02:48:47 +0200
Subject: fix domain completion

---
 lib/completion.js | 39 ++++++++++++++++++++++++++++-----------
 1 file changed, 28 insertions(+), 11 deletions(-)

diff --git a/lib/completion.js b/lib/completion.js
index 8b63fab0..81ce2f04 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -499,29 +499,43 @@ var completion = (function() {
 
   DomainCompletionSource.prototype.withDomains = function(callback) {
     var self = this;
+    function buildResult() {
+      return Object.keys(self.domains).map(function(dom) {
+        return [dom, self.domains[dom]];
+      });
+    }
     if (self.domains !== null)
-      return callback(Object.keys(self.domains));
+      return callback(buildResult());
 
     self.domains = {};
 
-    function processDomain(domain) {
-      self.domains[domain] = true;
+    function processDomain(domain, https) {
+      // non-www version is preferrable, so check if we have it already
+      if (domain.indexOf('www.') == 0 && self.domains.hasOwnProperty(domain.slice(4)))
+        domain = domain.slice(4);
+
+      // HTTPS is preferrable
+      https = https || self.domains[domain] || self.domains['www.' + domain];
+
+      self.domains[domain] = !!https;
       delete self.domains['www.' + domain];
     }
-    function extractDomain(url) { return url.split('/')[2]; }
+    function processUrl(url) {
+      parts = url.split('/');
+      processDomain(parts[2], parts[0] == 'https:');
+    }
 
     historyCache.use(function(history) {
       history.forEach(function(item) {
-        processDomain(extractDomain(item.url));
+        processUrl(item.url);
       });
     });
-    // delete redundant www. domains
-    Object.keys(self.domains).forEach(function(domain) { processDomain(domain); });
 
     chrome.history.onVisited.addListener(function(item) {
-      processDomain(extractDomain(item.url));
+      processUrl(item.url);
     });
-    callback(Object.keys(self.domains));
+
+    callback(buildResult());
   }
 
   DomainCompletionSource.prototype.refresh = function() { }
@@ -529,7 +543,10 @@ var completion = (function() {
     var best = null;
     this.withDomains(function(domains) {
       var bestOffset = 1000;
-      domains.forEach(function(domain) {
+      domains.forEach(function(result) {
+        var domain = result[0];
+        var protocol = result[1] ? 'https' : 'http';
+
         var offset = domain.indexOf(query);
         if (offset < 0 || offset >= bestOffset)
           return;
@@ -539,7 +556,7 @@ var completion = (function() {
         best = new LazyCompletion(-1.5, function() {
           return {
             html:   createCompletionHtml('site', domain),
-            action: {func: 'completion.createActionOpenUrl', args: [utils.createFullUrl(domain)]},
+            action: {func: 'completion.createActionOpenUrl', args: [protocol + '://' + domain]},
           }});
       });
     });
-- 
cgit v1.2.3


From 549f38eb3dc994cff20e10eb69a2f155a498abdf Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 13 Apr 2012 04:20:45 +0200
Subject: change to real input box

---
 fuzzyMode.js | 33 ++++++++++++---------------------
 vimium.css   |  9 +++++++++
 2 files changed, 21 insertions(+), 21 deletions(-)

diff --git a/fuzzyMode.js b/fuzzyMode.js
index aab89e16..37107a07 100644
--- a/fuzzyMode.js
+++ b/fuzzyMode.js
@@ -39,8 +39,8 @@ var fuzzyMode = (function() {
     show: function(reverseAction) {
       this.reverseAction = reverseAction;
       this.box.style.display = 'block';
-      var self = this;
-      handlerStack.push({ keydown: function(event) { self.onKeydown(event); }});
+      this.input.focus();
+      handlerStack.push({ keydown: this.onKeydown.bind(this) });
     },
 
     hide: function() {
@@ -50,7 +50,7 @@ var fuzzyMode = (function() {
     },
 
     reset: function() {
-      this.query = '';
+      this.input.value = '';
       this.updateTimer = null;
       this.completions = [];
       this.selection = 0;
@@ -86,13 +86,6 @@ var fuzzyMode = (function() {
         this.updateSelection();
       }
 
-      else if (event.keyCode == keyCodes.backspace) {
-        if (this.query.length > 0) {
-          this.query = this.query.substr(0, this.query.length-1);
-          this.update();
-        }
-      }
-
       // refresh with F5
       else if (keyChar == 'f5') {
         this.completer.refresh();
@@ -110,12 +103,11 @@ var fuzzyMode = (function() {
           self.hide();
         });
       }
-
-      else if (keyChar.length == 1) {
-        this.query += keyChar;
-        this.update();
+      else {
+        return true; // pass through
       }
 
+      // it seems like we have to manually supress the event here and still return true...
       event.stopPropagation();
       event.preventDefault();
       return true;
@@ -123,8 +115,9 @@ var fuzzyMode = (function() {
 
     updateCompletions: function(callback) {
       var self = this;
-      //var start = Date.now();
-      this.completer.filter(this.query, this.maxResults, function(completions) {
+      query = this.input.value.replace(/^\s*/, '');
+
+      this.completer.filter(query, this.maxResults, function(completions) {
         self.completions = completions;
 
         // update completion list with the new data
@@ -141,9 +134,6 @@ var fuzzyMode = (function() {
     update: function(force, callback) {
       force = force || false; // explicitely default to asynchronous updating
 
-      this.query = this.query.replace(/^\s*/, '');
-      this.input.textContent = this.query;
-
       if (force) {
         // cancel scheduled update
         if (this.updateTimer !== null)
@@ -168,12 +158,13 @@ var fuzzyMode = (function() {
         '<div id="fuzzybox" class="vimiumReset">'+
           '<div class="input">'+
             '<span class="prompt">' + utils.escapeHtml(this.prompt) + '</span> '+
-            '<span class="query"></span></div>'+
+            '<input type="text" class="query"></span></div>'+
           '<ul></ul></div>');
       this.box.style.display = 'none';
       document.body.appendChild(this.box);
 
-      this.input          = document.querySelector("#fuzzybox .query");
+      this.input = document.querySelector("#fuzzybox .query");
+      this.input.addEventListener("input", function() { this.update(); }.bind(this));
       this.completionList = document.querySelector("#fuzzybox ul");
       this.completionList.style.display = 'none';
     },
diff --git a/vimium.css b/vimium.css
index 53bc50d8..774c0fd3 100644
--- a/vimium.css
+++ b/vimium.css
@@ -369,3 +369,12 @@ body.vimiumFindMode ::selection {
   font-size: inherit !important;
   font-family: inherit !important;
 }
+
+#fuzzybox .input .query {
+  font-size: inherit !important;
+  font-family: inherit !important;
+  color: inherit !important;
+  background: none;
+  outline: none;
+  border: none;
+}
-- 
cgit v1.2.3


From cbe44163f741b3b20ad06464f9dda80ed271bd15 Mon Sep 17 00:00:00 2001
From: Niklas Baumstark
Date: Fri, 13 Apr 2012 05:16:52 +0200
Subject: improve CSS, fix input width

---
 vimium.css | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/vimium.css b/vimium.css
index 774c0fd3..7d9ef3d1 100644
--- a/vimium.css
+++ b/vimium.css
@@ -293,6 +293,7 @@ body.vimiumFindMode ::selection {
 #fuzzybox {
   position: fixed !important;
   width: 80% !important;
+  min-width: 400px !important;
   top: 70px !important;
   left: 50% !important;
   margin: 0 0 0 -40% !important;
@@ -374,7 +375,8 @@ body.vimiumFindMode ::selection {
   font-size: inherit !important;
   font-family: inherit !important;
   color: inherit !important;
-  background: none;
-  outline: none;
-  border: none;
+  background: none !important;
+  outline: none !important;
+  border: none !important;
+  width: 90% !important;
 }
-- 
cgit v1.2.3