A WIP rewrite of completion in the vomnibar.

The purpose of this refactor is to simplify the contract so it's easier
to modify, and to make some substantial usability improvements.

One of the key differences is that matching is no longer fuzzy. If you
want to search more than one term, separate them by spaces. This matches
the behavior in Firefox.

While fuzzy matching is a nice experience for a limited set of known
items (like files in the current project), it doesn't work well for
a huge messy collection, like URLs in your history. The query "hello"
will match random stuff from your google search results for instance,
and it's hard to prune that noise using ranking intelligence.

5 files changed, 215 insertions, 22 deletions

diff --git a/background_page.html b/background_page.html
index a1af1396..709a6633 100644
--- a/background_page.html
+++ b/background_page.html
@@ -53,26 +53,12 @@
   var tabLoadedHandlers = {}; // tabId -> function()
 
   var completionSources = {
-    smart:     new completion.SmartKeywordCompleter({
-      "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.DomainCompleter(),
-    bookmarks: new completion.FuzzyBookmarkCompleter(),
-    history:   new completion.FuzzyHistoryCompleter(20000),
-    tabs:      new completion.FuzzyTabCompleter(),
-  }
+    bookmarks: new BookmarkCompleter(),
+    history: new HistoryCompleter()
+  };
+
   var completers = {
-    omni: new completion.MultiCompleter([
-                  completionSources.domain,
-                  completionSources.smart,
-                  completionSources.bookmarks,
-                  completionSources.history,
-                  ], 1),
-    tabs: new completion.MultiCompleter([ completionSources.tabs ], 0),
+    omni: new MultiCompleter([completionSources.bookmarks, completionSources.history])
   };
 
   chrome.extension.onConnect.addListener(function(port, name) {
@@ -305,7 +291,8 @@
   }
 
   function filterCompleter(args, port) {
-    completers[args.name].filter(args.query, args.maxResults, function(results) {
+    var queryTerms = args.query == "" ? [] : args.query.split(" ");
+    completers[args.name].filter(queryTerms, function(results) {
       port.postMessage({ id: args.id, results: results });
     });
   }
diff --git a/background_scripts/completion.coffee b/background_scripts/completion.coffee
new file mode 100644
index 00000000..15725b62
--- /dev/null
+++ b/background_scripts/completion.coffee
@@ -0,0 +1,148 @@
+class Suggestion
+  # - type: one of [bookmark, history, tab].
+  # - action: one of [navigateToUrl, switchToTab].
+  # TODO(philc): remove action. I don't think we need it here.
+  constructor: (@queryTerms, @type, @url, @title, @action) ->
+
+  generateHtml: ->
+    @html ||=
+      "<div class='topHalf'>
+         <span class='source'>#{@type}</span>
+         <span class='title'>#{@highlightTerms(utils.escapeHtml(@title))}</span>
+       </div>
+       <div class='bottomHalf'><span class='url'>#{@shortenUrl(@highlightTerms(@url))}</span></div>"
+
+  shortenUrl: (url) ->
+    @stripTrailingSlash(url).replace(/^http:\/\//, "")
+
+  stripTrailingSlash: (url) ->
+    url = url.substring(url, url.length - 1) if url[url.length - 1] == "/"
+    url
+
+  # Wraps each occurence of the query terms in the given string in a <span>.
+  highlightTerms: (string) ->
+    for term in @queryTerms
+      regexp = @escapeRegexp(term)
+      string = string.replace(regexp, "<span class='match'>$&</span>")
+    string
+
+  # Creates a Regexp from the given string, with all special Regexp characters escaped.
+  escapeRegexp: (string) ->
+    # Taken from http://stackoverflow.com/questions/3446170/escape-string-for-use-in-javascript-regex
+    Suggestion.escapeRegExp ||= /[\-\[\]\/\{\}\(\)\*\+\?\.\\\^\$\|]/g
+    new RegExp(string.replace(Suggestion.escapeRegExp, "\\$&"), "i")
+
+  computeRelevancy: ->
+    # TODO(philc):
+    1
+
+class BookmarkCompleter
+  currentSearch: null
+  # These bookmarks are loaded asynchronously when refresh() is called.
+  bookmarks: null
+
+  filter: (@queryTerms, @onComplete) ->
+    @currentSearch = { queryTerms: @queryTerms, onComplete: @onComplete }
+    @performSearch() if @bookmarks
+
+  onBookmarksLoaded: -> @performSearch() if @currentSearch
+
+  performSearch: ->
+    results = @bookmarks.filter (bookmark) =>
+        RankingUtils.matches(@currentSearch.queryTerms, bookmark.url, bookmark.title)
+    suggestions = results.map (bookmark) =>
+      new Suggestion(@currentSearch.queryTerms, "bookmark", bookmark.url, bookmark.title, "navigateToUrl")
+    onComplete = @currentSearch.onComplete
+    @currentSearch = null
+    onComplete(suggestions)
+
+  refresh: ->
+    @bookmarks = null
+    chrome.bookmarks.getTree (bookmarks) =>
+      @bookmarks = @traverseBookmarks(bookmarks).filter((bookmark) -> bookmark.url?)
+      @onBookmarksLoaded()
+
+  # Traverses the bookmark hierarchy, and retuns a flattened list of all bookmarks in the tree.
+  traverseBookmarks: (bookmarks) ->
+    results = []
+    toVisit = bookmarks
+    while toVisit.length > 0
+      bookmark = toVisit.shift()
+      results.push(bookmark)
+      toVisit.push.apply(toVisit, bookmark.children) if (bookmark.children)
+
+    results
+
+class HistoryCompleter
+  filter: (queryTerms, onComplete) ->
+    @currentSearch = { queryTerms: @queryTerms, onComplete: @onComplete }
+    results = []
+    HistoryCache.use (history) ->
+      results = history.filter (entry) -> RankingUtils.matches(queryTerms, entry.url, entry.title)
+    suggestions = results.map (entry) =>
+      new Suggestion(queryTerms, "history", entry.url, entry.title, "navigateToUrl")
+    onComplete(suggestions)
+
+  refresh: ->
+
+class MultiCompleter
+  constructor: (@completers) ->
+    @maxResults = 10 # TODO(philc): Should this be configurable?
+
+  refresh: -> completer.refresh() for completer in @completers
+
+  filter: (queryTerms, onComplete) ->
+    suggestions = []
+    completersFinished = 0
+    for completer in @completers
+      # Call filter() on every source completer and wait for them all to finish before returning results.
+      completer.filter queryTerms, (newSuggestions) =>
+        suggestions = suggestions.concat(newSuggestions)
+        completersFinished += 1
+        if completersFinished >= @completers.length
+          results = @sortSuggestions(suggestions)[0...@maxResults]
+          result.generateHtml() for result in results
+          onComplete(results)
+
+  sortSuggestions: (suggestions) ->
+    for suggestion in suggestions
+      suggestion.computeRelevancy(@queryTerms)
+    suggestions.sort (a, b) -> a.relevancy - b.relevancy
+    suggestions
+
+RankingUtils =
+  # Whether the given URL or title match any one of the query terms. This is used to prune out irrelevant
+  # suggestions before we try to rank them.
+  matches: (queryTerms, url, title) ->
+    return false if queryTerms.length == 0
+    for term in queryTerms
+      return false unless title.indexOf(term) >= 0 || url.indexOf(term) >= 0
+    true
+
+# Provides cached access to Chrome's history.
+HistoryCache =
+  size: 20000
+  history: null # An array of History items returned from Chrome.
+
+  use: (callback) ->
+    return @fetchHistory(callback) unless @history?
+    callback(@history)
+
+  fetchHistory: (callback) ->
+    return @callbacks.push(callback) if @callbacks
+    @callbacks = [callback]
+    chrome.history.search { text: "", maxResults: @size, startTime: 0 }, (history) =>
+      # sorting in ascending order. We will push new items on to the end as the user navigates to new pages.
+      history.sort((a, b) -> (a.lastVisitTime || 0) - (b.lastVisitTime || 0))
+      @history = history
+      chrome.history.onVisited.addListener (newSite) =>
+        firstTimeVisit = (newSite.visitedCount == 1)
+        @history.push(newSite) if firstTimeVisit
+      callback(@history) for callback in @callbacks
+      @callbacks = null
+
+root = exports ? window
+root.Suggestion = Suggestion
+root.BookmarkCompleter = BookmarkCompleter
+root.MultiCompleter = MultiCompleter
+root.HistoryCompleter = HistoryCompleter
\ No newline at end of file
diff --git a/tests/completion_test.coffee b/tests/completion_test.coffee
new file mode 100644
index 00000000..eb833ecf
--- /dev/null
+++ b/tests/completion_test.coffee
@@ -0,0 +1,53 @@
+require "./test_helper.js"
+extend(global, require "../lib/utils.js")
+extend(global, require "../background_scripts/completion.js")
+
+global.chrome = {}
+
+context "bookmark completer",
+  setup ->
+    @bookmark2 = { title: "bookmark2", url: "bookmark2.com" }
+    @bookmark1 = { title: "bookmark1", url: "bookmark1.com", children: [@bookmark2] }
+    global.chrome.bookmarks =
+      getTree: (callback) => callback([@bookmark1])
+
+    @completer = new BookmarkCompleter()
+
+  should "flatten a list of bookmarks", ->
+    result = @completer.traverseBookmarks([@bookmark1])
+    assert.arrayEqual [@bookmark1, @bookmark2], @completer.traverseBookmarks([@bookmark1])
+
+  should "return matching bookmarks when searching", ->
+    @completer.refresh()
+    @completer.filter(["mark2"], (@results) =>)
+    assert.arrayEqual [@bookmark2.url], @results.map (suggestion) -> suggestion.url
+
+context "history completer",
+  setup ->
+    @history1 = { title: "history1", url: "history1.com" }
+    @history2 = { title: "history2", url: "history2.com" }
+
+    global.chrome.history =
+      search: (options, callback) => callback([@history1, @history2])
+      onVisited: { addListener: -> }
+
+    @completer = new HistoryCompleter()
+
+  should "return matching history entries when searching", ->
+    @completer.filter(["story1"], (@results) =>)
+    assert.arrayEqual [@history1.url], @results.map (entry) -> entry.url
+
+context "suggestions",
+  should "escape html in page titles", ->
+    suggestion = new Suggestion(["queryterm"], "tab", "url", "title <span>", "action")
+    assert.isTrue suggestion.generateHtml().indexOf("title &lt;span&gt;") >= 0
+
+  should "highlight query words", ->
+    suggestion = new Suggestion(["ninja"], "tab", "url", "ninjawords", "action")
+    assert.isTrue suggestion.generateHtml().indexOf("<span class='match'>ninja</span>words") >= 0
+
+  should "shorten urls", ->
+    suggestion = new Suggestion(["queryterm"], "tab", "http://ninjawords.com", "ninjawords", "action")
+    assert.equal -1, suggestion.generateHtml().indexOf("http://ninjawords.com")
+
+Tests.run()
\ No newline at end of file
diff --git a/tests/test_helper.coffee b/tests/test_helper.coffee
new file mode 100644
index 00000000..237f8e24
--- /dev/null
+++ b/tests/test_helper.coffee
@@ -0,0 +1,5 @@
+require("./shoulda.js/shoulda.js")
+global.extend = (hash1, hash2) ->
+  for key of hash2
+    hash1[key] = hash2[key]
+  hash1
\ No newline at end of file
diff --git a/vimium.css b/vimium.css
index 52d8f1aa..31092542 100644
--- a/vimium.css
+++ b/vimium.css
@@ -327,7 +327,7 @@ body.vimiumFindMode ::selection {
 
 #vomnibar li .url { color: #224684 !important; }
 
-#vomnibar li .fuzzyMatch {
+#vomnibar li .match {
   font-size: inherit !important;
   font-family: inherit !important;
   font-weight: bold !important;
@@ -342,7 +342,7 @@ body.vimiumFindMode ::selection {
   font-family: inherit !important;
 }
 #vomnibar li em { font-style: italic !important; }
-#vomnibar li em .fuzzyMatch, #vomnibar li .title .fuzzyMatch {
+#vomnibar li em .match, #vomnibar li .title .match {
   color: #333 !important;
   text-decoration: underline !important;
 }