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.

1 files changed, 148 insertions, 0 deletions

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