Merge pull request #459 from niklasb/fuzzy

Vimium Omnibox implementation, with fuzzy completion

8 files changed, 1087 insertions, 29 deletions

diff --git a/background_page.html b/background_page.html
index d8d3f75b..9ce9fe22 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();
 
@@ -26,7 +27,8 @@
     returnScrollPosition: handleReturnScrollPosition,
     getCurrentTabUrl:     getCurrentTabUrl,
     settings:             handleSettings,
-    getBookmarks:         getBookmarks
+    getBookmarks:         getBookmarks,
+    filterCompleter:      filterCompleter,
   };
 
   var sendRequestHandlers = {
@@ -41,7 +43,9 @@
     updateScrollPosition: handleUpdateScrollPosition,
     copyToClipboard: copyToClipboard,
     isEnabledForUrl: isEnabledForUrl,
-    saveHelpDialogSettings: saveHelpDialogSettings
+    saveHelpDialogSettings: saveHelpDialogSettings,
+    selectSpecificTab: selectSpecificTab,
+    refreshCompleter: refreshCompleter,
   };
 
   // Event handlers
@@ -49,6 +53,29 @@
   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) } ],
+      }),
+    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,
+                  ], 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
@@ -70,7 +97,6 @@
 
     if (portHandlers[port.name])
       port.onMessage.addListener(portHandlers[port.name]);
-
   });
 
   chrome.extension.onRequest.addListener(function (request, sender, sendResponse) {
@@ -257,6 +283,13 @@
     Clipboard.copy(request.data);
   }
 
+  /**
+    * Selects the tab with the ID specified in request.id
+    */
+  function selectSpecificTab(request) {
+    chrome.tabs.update(request.id, { selected: true });
+  }
+
   /*
    * Used by the content scripts to get settings from the local storage.
    */
@@ -276,6 +309,27 @@
     })
   }
 
+  function refreshCompleter(request) {
+    completers[request.name].refresh();
+  }
+
+  function filterCompleter(args, port) {
+    completers[args.name].filter(args.query, args.maxResults, function(results) {
+      port.postMessage({ id: args.id, results: 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..727bf3c7 100644
--- a/commands.js
+++ b/commands.js
@@ -144,7 +144,12 @@ function clearKeyMappingsAndSetDefaults() {
     "b": "activateBookmarkFindMode",
     "B": "activateBookmarkFindModeToOpenInNewTab",
 
-    "gf": "nextFrame"
+    "o": "fuzzyMode.activateAll",
+    "O": "fuzzyMode.activateAllNewTab",
+
+    "T": "fuzzyMode.activateTabs",
+
+    "gf": "nextFrame",
   };
 
   for (var key in defaultKeyMappings)
@@ -211,6 +216,10 @@ var commandDescriptions = {
   activateBookmarkFindMode: ["Open a bookmark in the current tab"],
   activateBookmarkFindModeToOpenInNewTab: ["Open a bookmark in a 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)"],
+  'fuzzyMode.activateTabs': ["Go to a tab in this window (fuzzy)"],
+
   nextFrame: ["Cycle forward to the next frame on the page", { background: true, passCountToFunction: true }]
 };
 
@@ -230,6 +239,7 @@ var commandGroups = {
      "enterInsertMode", "focusInput",
      "linkHints.activateMode", "linkHints.activateModeToOpenInNewTab", "linkHints.activateModeWithQueue",
      "activateBookmarkFindMode", "activateBookmarkFindModeToOpenInNewTab",
+     "fuzzyMode.activateAll", "fuzzyMode.activateAllNewTab", "fuzzyMode.activateTabs",
      "goPrevious", "goNext", "nextFrame"],
   findCommands: ["enterFindMode", "performFind", "performBackwardsFind"],
   historyNavigation:
diff --git a/fuzzyMode.js b/fuzzyMode.js
new file mode 100644
index 00000000..37107a07
--- /dev/null
+++ b/fuzzyMode.js
@@ -0,0 +1,180 @@
+var fuzzyMode = (function() {
+  var fuzzyBox = null;  // the dialog instance for this window
+  var completers = { };
+
+  function getCompleter(name) {
+    if (!(name in completers))
+      completers[name] = new completion.BackgroundCompleter(name);
+    return completers[name];
+  }
+
+  /** Trigger the fuzzy mode dialog */
+  function start(name, reverseAction, refreshInterval) {
+    var completer = getCompleter(name);
+    if (!fuzzyBox)
+      fuzzyBox = new FuzzyBox(10);
+    completer.refresh();
+    fuzzyBox.setCompleter(completer);
+    fuzzyBox.setRefreshInterval(refreshInterval);
+    fuzzyBox.show(reverseAction);
+  }
+
+  /** User interface for fuzzy completion */
+  var FuzzyBox = function(maxResults) {
+    this.prompt = '>';
+    this.maxResults = maxResults;
+    this.refreshInterval = 0;
+    this.initDom();
+  }
+  FuzzyBox.prototype = {
+    setCompleter: function(completer) {
+      this.completer = completer;
+      this.reset();
+    },
+
+    setRefreshInterval: function(refreshInterval) {
+      this.refreshInterval = refreshInterval;
+    },
+
+    show: function(reverseAction) {
+      this.reverseAction = reverseAction;
+      this.box.style.display = 'block';
+      this.input.focus();
+      handlerStack.push({ keydown: this.onKeydown.bind(this) });
+    },
+
+    hide: function() {
+      this.box.style.display = 'none';
+      this.completionList.style.display = 'none';
+      handlerStack.pop();
+    },
+
+    reset: function() {
+      this.input.value = '';
+      this.updateTimer = null;
+      this.completions = [];
+      this.selection = 0;
+      this.update(true);
+    },
+
+    updateSelection: function() {
+      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' : '';
+    },
+
+    onKeydown: function(event) {
+      var self = this;
+      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();
+      }
+
+      // refresh with F5
+      else if (keyChar == 'f5') {
+        this.completer.refresh();
+        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, function() {
+          var alternative = (event.shiftKey || isPrimaryModifierKey(event));
+          if (self.reverseAction)
+            alternative = !alternative;
+          self.completions[self.selection].action[alternative ? 1 : 0]();
+          self.hide();
+        });
+      }
+      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;
+    },
+
+    updateCompletions: function(callback) {
+      var self = this;
+      query = this.input.value.replace(/^\s*/, '');
+
+      this.completer.filter(query, this.maxResults, function(completions) {
+        self.completions = completions;
+
+        // update completion list with the new data
+        self.completionList.innerHTML = completions.map(function(completion) {
+          return '<li>' + completion.html + '</li>';
+        }).join('');
+
+        self.completionList.style.display = self.completions.length > 0 ? 'block' : 'none';
+        self.updateSelection();
+        if (callback) callback();
+      });
+    },
+
+    update: function(force, callback) {
+      force = force || false; // explicitely default to asynchronous updating
+
+      if (force) {
+        // cancel scheduled update
+        if (this.updateTimer !== null)
+          window.clearTimeout(this.updateTimer);
+        this.updateCompletions(callback);
+      } 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)
+        this.updateTimer = setTimeout(function() {
+          self.updateCompletions(callback);
+          self.updateTimer = null;
+        }, this.refreshInterval);
+      }
+    },
+
+    initDom: function() {
+      this.box = utils.createElementFromHtml(
+        '<div id="fuzzybox" class="vimiumReset">'+
+          '<div class="input">'+
+            '<span class="prompt">' + utils.escapeHtml(this.prompt) + '</span> '+
+            '<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.addEventListener("input", function() { this.update(); }.bind(this));
+      this.completionList = document.querySelector("#fuzzybox ul");
+      this.completionList.style.display = 'none';
+    },
+  }
+
+  // public interface
+  return {
+    activateAll:       function() { start('omni', false, 100); },
+    activateAllNewTab: function() { start('omni', true,  100);  },
+    activateTabs:      function() { start('tabs', false, 0);  },
+  }
+
+})();
diff --git a/lib/completion.js b/lib/completion.js
new file mode 100644
index 00000000..81ce2f04
--- /dev/null
+++ b/lib/completion.js
@@ -0,0 +1,644 @@
+var completion = (function() {
+
+  //============ Helper functions and objects ============//
+
+  /** Singleton object that provides helpers and caching for fuzzy completion. */
+  var fuzzyMatcher = (function() {
+    var self = {};
+
+    self.timeToClean = 0;
+    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) {
+      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
+     * 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. 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.getMatchGroups = function(query, str) {
+      query = self.normalize(query);
+      if (query.length == 0)
+        return str.length ? [str] : [];
+      if (query.length > 15) {
+        // for long query strings, the method is much too inefficient, so fall
+        // back to the less accurate regex matching
+        return self.getMatcher(query).exec(str).slice(1);
+      }
+
+      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.getMatchGroups(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 */
+    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) {
+            var length = i - start;
+            sum += length * length;
+            break;
+          }
+        }
+      }
+      return sum * sum * sum;
+    }
+
+    /** Trims the size of the caches to the configured size using a FIFO algorithm. */
+    self.cleanCache = function() {
+      // 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
+     * 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. 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];
+    }
+
+    /** 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.
+     */
+    self.filter = function(query, source, getValue, id) {
+      if (!(id in self.filterCache))
+        self.filterCache[id] = {};
+
+      // 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))
+          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 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 (specificity < optSpecificity) {
+          source = self.filterCache[id][key];
+          optSpecificity = specificity;
+        }
+      }
+
+      // don't clean up the caches every iteration
+      if (++self.timeToClean > 100) {
+        self.timeToClean = 0;
+        self.cleanCache();
+      }
+
+      var matcher = self.getMatcher(query);
+      var filtered = source.filter(function(x) { return matcher.test(getValue(x)) });
+      self.filterCache[id][query] = filtered;
+      return filtered;
+    }
+
+    return self;
+  })();
+
+  var htmlRegex = /<[^>]*>|&[a-z]+;/gi;
+
+  /** 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)
+      return str.replace(htmlRegex, '');
+
+    var match = str.match(htmlRegex);
+    if (!match) return;
+    match.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. */
+  function createActionOpenUrl(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) ];
+  }
+
+  /** 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 || '';
+    // 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(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 */
+  function createConstantFunction(x) {
+    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;
+  }
+
+  /** 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() {
+    this.id = utils.createUniqueId();
+    this.reset();
+    this.resultsReady = this.fallbackReadyCallback = function(results) {
+      this.completions = results;
+    }
+  }
+  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
+     * 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 || {func: 'completion.createActionOpenUrl', args: [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) {
+        callback(self.processResults(query, results));
+      }
+
+      // are the results ready?
+      if (this.completions !== null) {
+        // yes: call the callback synchronously
+        handler(this.completions);
+      } else {
+        // no: register the handler as a callback
+        this.resultsReady = function(results) {
+          handler(results);
+          self.resultsReady = self.fallbackReadyCallback;
+          self.resultsReady(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 SmartCompletionSource = function(commands) {
+    commands = commands || {};
+    var commandKeys = Object.keys(commands);
+
+    this.refresh = function() { };
+
+    /** 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);
+
+        // this will appear even before the URL/search suggestion
+        return new LazyCompletion(-2, function() {
+          return {
+            html:   createCompletionHtml(desc, term),
+            action: {func: 'completion.createActionOpenUrl', args: [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.getUrlOrSearchSuggestion = function(query, suggestions) {
+      // trim query
+      query = query.replace(/^\s+|\s+$/g, '');
+      var isUrl = utils.isUrl(query);
+
+      return new LazyCompletion(-1, function() {
+        return {
+          html: createCompletionHtml(isUrl ? 'goto' : 'search', query),
+          action: {func: 'completion.createActionOpenUrl', args: isUrl ? [utils.createFullUrl(query)]
+                                                                       : [utils.createSearchUrl(query)]},
+        }});
+    }
+
+    this.filter = function(query, callback) {
+      suggestions = this.getCommandSuggestions(query);
+      suggestions.push(this.getUrlOrSearchSuggestion(query));
+      callback(suggestions);
+    }
+  }
+
+  /** A fuzzy bookmark completer */
+  var FuzzyBookmarkCompletionSource = function() {
+    AsyncCompletionSource.call(this);
+  }
+  utils.extend(AsyncCompletionSource, FuzzyBookmarkCompletionSource);
+
+  FuzzyBookmarkCompletionSource.prototype.traverseTree = function(bookmarks, results) {
+    var self = this;
+    bookmarks.forEach(function(bookmark) {
+      results.push(bookmark);
+      if (bookmark.children === undefined)
+        return;
+      self.traverseTree(bookmark.children, results);
+    });
+  }
+
+  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.maxResults = maxResults;
+  }
+  utils.extend(AsyncCompletionSource, FuzzyHistoryCompletionSource);
+
+  FuzzyHistoryCompletionSource.prototype.refresh = function() {
+    var self = this;
+    self.reset();
+
+    historyCache.use(function(history) {
+      self.resultsReady(history.slice(-self.maxResults).map(function(item) {
+        return self.createInternalMatch('history', item);
+      }))
+    });
+  }
+
+  /** A fuzzy tab completer */
+  var FuzzyTabCompletionSource = function() {
+    AsyncCompletionSource.call(this);
+  }
+  utils.extend(AsyncCompletionSource, FuzzyTabCompletionSource);
+
+  FuzzyTabCompletionSource.prototype.refresh = function() {
+    var self = this;
+    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] });
+      }));
+    });
+  }
+
+  /** 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;
+    function buildResult() {
+      return Object.keys(self.domains).map(function(dom) {
+        return [dom, self.domains[dom]];
+      });
+    }
+    if (self.domains !== null)
+      return callback(buildResult());
+
+    self.domains = {};
+
+    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 processUrl(url) {
+      parts = url.split('/');
+      processDomain(parts[2], parts[0] == 'https:');
+    }
+
+    historyCache.use(function(history) {
+      history.forEach(function(item) {
+        processUrl(item.url);
+      });
+    });
+
+    chrome.history.onVisited.addListener(function(item) {
+      processUrl(item.url);
+    });
+
+    callback(buildResult());
+  }
+
+  DomainCompletionSource.prototype.refresh = function() { }
+  DomainCompletionSource.prototype.filter = function(query, callback) {
+    var best = null;
+    this.withDomains(function(domains) {
+      var bestOffset = 1000;
+      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;
+
+        // found a new optimum
+        bestOffset = offset;
+        best = new LazyCompletion(-1.5, function() {
+          return {
+            html:   createCompletionHtml('site', domain),
+            action: {func: 'completion.createActionOpenUrl', args: [protocol + '://' + 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' });
+  }
+  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 search. */
+  var MultiCompleter = function(sources, queryThreshold) {
+    if (queryThreshold === undefined)
+      queryThreshold = 1; // default
+    this.sources = sources;
+    this.queryThreshold = queryThreshold;
+  }
+  MultiCompleter.prototype = {
+    refresh: function() {
+      this.sources.forEach(function(x) { x.refresh(); });
+    },
+
+    filter: function(query, maxResults, callback) {
+      if (query.length < this.queryThreshold) {
+        callback([]);
+        return;
+      }
+
+      var self = this;
+      var all = [];
+      var counter = this.sources.length;
+
+      this.sources.forEach(function(source) {
+        source.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; });
+          // evalulate lazy completions for the top n results
+          callback(all.slice(0, maxResults).map(function(result) { return result.build(); }));
+        });
+      });
+    }
+  }
+
+  // public interface
+  return {
+    FuzzyBookmarkCompletionSource: FuzzyBookmarkCompletionSource,
+    FuzzyHistoryCompletionSource: FuzzyHistoryCompletionSource,
+    FuzzyTabCompletionSource: FuzzyTabCompletionSource,
+    SmartCompletionSource: SmartCompletionSource,
+    DomainCompletionSource: DomainCompletionSource,
+    MultiCompleter: MultiCompleter,
+    BackgroundCompleter: BackgroundCompleter,
+    createActionOpenUrl: createActionOpenUrl,
+    createActionSwitchToTab: createActionSwitchToTab,
+  };
+})()
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..7ed7c9ad 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -20,18 +20,68 @@ 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);
+  },
+
+  /** 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");
+    tmp.innerHTML = html;
+    return tmp.firstChild;
+  },
+
+  /** Escapes HTML */
+  escapeHtml: function(html) {
+    var tmp = document.createElement("div");
+    tmp.textContent = html;
+    return tmp.innerHTML;
+  },
+
   /**
-   * 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(
@@ -47,46 +97,65 @@ 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 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: use as search query
-    return utils.createSearchUrl(str);
+    // fallback: no URL
+    return false
+  },
+
+  /**
+   * Creates a search URL from the given :query.
+   */
+  createSearchUrl: function(query) {
+    // we need to escape explictely to encode characters like "+" correctly
+    return "http://www.google.com/search?q=" + encodeURIComponent(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) {
+    // trim str
+    str = str.replace(/^\s+|\s+$/g, '');
+    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 c5bee6a7..93be04c9 100644
--- a/vimium.css
+++ b/vimium.css
@@ -282,4 +282,101 @@ div.vimium-completions div.vimium-noResults{
 
 body.vimiumFindMode ::selection {
   background: #ff9632;
+};
+
+/* fuzzymode CSS */
+
+#fuzzybox ol, #fuzzybox ul {
+  list-style: none !important;
+}
+
+#fuzzybox {
+  position: fixed !important;
+  width: 80% !important;
+  min-width: 400px !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 !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 !important;
+  line-height: 1.1em !important;
+  padding: 7px !important;
+  margin: 0 -7px 0 -7px !important;
+  font-size: 18px !important;
+  color: #ddd !important;
+}
+
+#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;
+}
+#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;
+  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;
+}
+
+#fuzzybox .input {
+  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;
+}
+
+#fuzzybox .input .query {
+  font-size: inherit !important;
+  font-family: inherit !important;
+  color: inherit !important;
+  background: none !important;
+  outline: none !important;
+  border: none !important;
+  width: 90% !important;
 }