Merge branch 'search-engine-completion-v5'

5 files changed, 595 insertions, 150 deletions

diff --git a/background_scripts/completion.coffee b/background_scripts/completion.coffee
index 6a1c0d30..23526f85 100644
--- a/background_scripts/completion.coffee
+++ b/background_scripts/completion.coffee
@@ -5,26 +5,41 @@
 # The Vomnibox frontend script makes a "filterCompleter" request to the background page, which in turn calls
 # filter() on each these completers.
 #
-# A completer is a class which has two functions:
+# A completer is a class which has three functions:
 #  - filter(query, onComplete): "query" will be whatever the user typed into the Vomnibox.
 #  - refresh(): (optional) refreshes the completer's data source (e.g. refetches the list of bookmarks).
-
-# A Suggestion is a bookmark or history entry which matches the current query.
-# It also has an attached "computeRelevancyFunction" which determines how well this item matches the given
-# query terms.
+#  - cancel(): (optional) cancels any pending, cancelable action.
 class Suggestion
-  showRelevancy: false # Set this to true to render relevancy when debugging the ranking scores.
-
-  # - type: one of [bookmark, history, tab].
-  # - computeRelevancyFunction: a function which takes a Suggestion and returns a relevancy score
-  #   between [0, 1]
-  # - extraRelevancyData: data (like the History item itself) which may be used by the relevancy function.
-  constructor: (@queryTerms, @type, @url, @title, @computeRelevancyFunction, @extraRelevancyData) ->
-    @title ||= ""
-    # When @autoSelect is truthy, the suggestion is automatically pre-selected in the vomnibar.
+  showRelevancy: true # Set this to true to render relevancy when debugging the ranking scores.
+
+  constructor: (@options) ->
+    # Required options.
+    @queryTerms = null
+    @type = null
+    @url = null
+    @relevancyFunction = null
+    # Other options.
+    @title = ""
+    # Extra data which will be available to the relevancy function.
+    @relevancyData = null
+    # If @autoSelect is truthy, then this suggestion is automatically pre-selected in the vomnibar.  There may
+    # be at most one such suggestion.
     @autoSelect = false
-
-  computeRelevancy: -> @relevancy = @computeRelevancyFunction(this)
+    # If truthy (and @autoSelect is truthy too), then this suggestion is always pre-selected when the query
+    # changes.  There may be at most one such suggestion.
+    @forceAutoSelect = false
+    # If @highlightTerms is true, then we highlight matched terms in the title and URL.
+    @highlightTerms = true
+    # If @insertText is a string, then the indicated text is inserted into the vomnibar input when the
+    # suggestion is selected.
+    @insertText = null
+
+    extend this, @options
+
+  computeRelevancy: ->
+    # We assume that, once the relevancy has been set, it won't change.  Completers must set either @relevancy
+    # or @relevancyFunction.
+    @relevancy ?= @relevancyFunction this
 
   generateHtml: ->
     return @html if @html
@@ -34,10 +49,10 @@ class Suggestion
       """
       <div class="vimiumReset vomnibarTopHalf">
          <span class="vimiumReset vomnibarSource">#{@type}</span>
-         <span class="vimiumReset vomnibarTitle">#{@highlightTerms(Utils.escapeHtml(@title))}</span>
+         <span class="vimiumReset vomnibarTitle">#{@highlightQueryTerms Utils.escapeHtml @title}</span>
        </div>
        <div class="vimiumReset vomnibarBottomHalf">
-        <span class="vimiumReset vomnibarUrl">#{@shortenUrl(@highlightTerms(Utils.escapeHtml(@url)))}</span>
+        <span class="vimiumReset vomnibarUrl">#{@shortenUrl @highlightQueryTerms Utils.escapeHtml @url}</span>
         #{relevancyHtml}
       </div>
       """
@@ -48,6 +63,11 @@ class Suggestion
     a.href = url
     a.protocol + "//" + a.hostname
 
+  getHostname: (url) ->
+    a = document.createElement 'a'
+    a.href = url
+    a.hostname
+
   shortenUrl: (url) -> @stripTrailingSlash(url).replace(/^https?:\/\//, "")
 
   stripTrailingSlash: (url) ->
@@ -77,7 +97,8 @@ class Suggestion
       textPosition += matchedText.length
 
   # Wraps each occurence of the query terms in the given string in a <span>.
-  highlightTerms: (string) ->
+  highlightQueryTerms: (string) ->
+    return string unless @highlightTerms
     ranges = []
     escapedTerms = @queryTerms.map (term) -> Utils.escapeHtml(term)
     for term in escapedTerms
@@ -115,7 +136,7 @@ class BookmarkCompleter
   # These bookmarks are loaded asynchronously when refresh() is called.
   bookmarks: null
 
-  filter: (@queryTerms, @onComplete) ->
+  filter: ({ @queryTerms }, @onComplete) ->
     @currentSearch = { queryTerms: @queryTerms, onComplete: @onComplete }
     @performSearch() if @bookmarks
 
@@ -133,11 +154,15 @@ class BookmarkCompleter
       else
         []
     suggestions = results.map (bookmark) =>
-      suggestionTitle = if usePathAndTitle then bookmark.pathAndTitle else bookmark.title
-      new Suggestion(@currentSearch.queryTerms, "bookmark", bookmark.url, suggestionTitle, @computeRelevancy)
+      new Suggestion
+        queryTerms: @currentSearch.queryTerms
+        type: "bookmark"
+        url: bookmark.url
+        title: if usePathAndTitle then bookmark.pathAndTitle else bookmark.title
+        relevancyFunction: @computeRelevancy
     onComplete = @currentSearch.onComplete
     @currentSearch = null
-    onComplete(suggestions)
+    onComplete suggestions
 
   refresh: ->
     @bookmarks = null
@@ -172,7 +197,7 @@ class BookmarkCompleter
     RankingUtils.wordRelevancy(suggestion.queryTerms, suggestion.url, suggestion.title)
 
 class HistoryCompleter
-  filter: (queryTerms, onComplete) ->
+  filter: ({ queryTerms }, onComplete) ->
     @currentSearch = { queryTerms: @queryTerms, onComplete: @onComplete }
     results = []
     HistoryCache.use (history) =>
@@ -181,18 +206,21 @@ class HistoryCompleter
           history.filter (entry) -> RankingUtils.matches(queryTerms, entry.url, entry.title)
         else
           []
-      suggestions = results.map (entry) =>
-        new Suggestion(queryTerms, "history", entry.url, entry.title, @computeRelevancy, entry)
-      onComplete(suggestions)
+      onComplete results.map (entry) =>
+        new Suggestion
+          queryTerms: queryTerms
+          type: "history"
+          url: entry.url
+          title: entry.title
+          relevancyFunction: @computeRelevancy
+          relevancyData: entry
 
   computeRelevancy: (suggestion) ->
-    historyEntry = suggestion.extraRelevancyData
+    historyEntry = suggestion.relevancyData
     recencyScore = RankingUtils.recencyScore(historyEntry.lastVisitTime)
     wordRelevancy = RankingUtils.wordRelevancy(suggestion.queryTerms, suggestion.url, suggestion.title)
     # Average out the word score and the recency. Recency has the ability to pull the score up, but not down.
-    score = (wordRelevancy + Math.max(recencyScore, wordRelevancy)) / 2
-
-  refresh: ->
+    (wordRelevancy + Math.max recencyScore, wordRelevancy) / 2
 
 # The domain completer is designed to match a single-word query which looks like it is a domain. This supports
 # the user experience where they quickly type a partial domain, hit tab -> enter, and expect to arrive there.
@@ -203,8 +231,8 @@ class DomainCompleter
   #     If `referenceCount` goes to zero, the domain entry can and should be deleted.
   domains: null
 
-  filter: (queryTerms, onComplete) ->
-    return onComplete([]) unless queryTerms.length == 1
+  filter: ({ queryTerms, query }, onComplete) ->
+    return onComplete [] unless queryTerms.length == 1 and not /\s$/.test query
     if @domains
       @performSearch(queryTerms, onComplete)
     else
@@ -212,20 +240,24 @@ class DomainCompleter
 
   performSearch: (queryTerms, onComplete) ->
     query = queryTerms[0]
-    domainCandidates = (domain for domain of @domains when domain.indexOf(query) >= 0)
-    domains = @sortDomainsByRelevancy(queryTerms, domainCandidates)
-    return onComplete([]) if domains.length == 0
-    topDomain = domains[0][0]
-    onComplete([new Suggestion(queryTerms, "domain", topDomain, null, @computeRelevancy)])
+    domains = (domain for domain of @domains when 0 <= domain.indexOf query)
+    domains = @sortDomainsByRelevancy queryTerms, domains
+    onComplete [
+      new Suggestion
+        queryTerms: queryTerms
+        type: "domain"
+        url: domains[0]?[0] ? "" # This is the URL or an empty string, but not null.
+        relevancy: 1
+      ].filter (s) -> 0 < s.url.length
 
   # Returns a list of domains of the form: [ [domain, relevancy], ... ]
   sortDomainsByRelevancy: (queryTerms, domainCandidates) ->
-    results = []
-    for domain in domainCandidates
-      recencyScore = RankingUtils.recencyScore(@domains[domain].entry.lastVisitTime || 0)
-      wordRelevancy = RankingUtils.wordRelevancy(queryTerms, domain, null)
-      score = (wordRelevancy + Math.max(recencyScore, wordRelevancy)) / 2
-      results.push([domain, score])
+    results =
+      for domain in domainCandidates
+        recencyScore = RankingUtils.recencyScore(@domains[domain].entry.lastVisitTime || 0)
+        wordRelevancy = RankingUtils.wordRelevancy queryTerms, domain, null
+        score = (wordRelevancy + Math.max(recencyScore, wordRelevancy)) / 2
+        [domain, score]
     results.sort (a, b) -> b[1] - a[1]
     results
 
@@ -258,9 +290,6 @@ class DomainCompleter
   parseDomainAndScheme: (url) ->
       Utils.hasFullUrlPrefix(url) and not Utils.hasChromePrefix(url) and url.split("/",3).join "/"
 
-  # Suggestions from the Domain completer have the maximum relevancy. They should be shown first in the list.
-  computeRelevancy: -> 1
-
 # TabRecency associates a logical timestamp with each tab id.  These are used to provide an initial
 # recency-based ordering in the tabs vomnibar (which allows jumping quickly between recently-visited tabs).
 class TabRecency
@@ -304,16 +333,20 @@ tabRecency = new TabRecency()
 
 # Searches through all open tabs, matching on title and URL.
 class TabCompleter
-  filter: (queryTerms, onComplete) ->
+  filter: ({ queryTerms }, onComplete) ->
     # NOTE(philc): We search all tabs, not just those in the current window. I'm not sure if this is the
     # correct UX.
     chrome.tabs.query {}, (tabs) =>
       results = tabs.filter (tab) -> RankingUtils.matches(queryTerms, tab.url, tab.title)
       suggestions = results.map (tab) =>
-        suggestion = new Suggestion(queryTerms, "tab", tab.url, tab.title, @computeRelevancy)
-        suggestion.tabId = tab.id
-        suggestion
-      onComplete(suggestions)
+        new Suggestion
+          queryTerms: queryTerms
+          type: "tab"
+          url: tab.url
+          title: tab.title
+          relevancyFunction: @computeRelevancy
+          tabId: tab.id
+      onComplete suggestions
 
   computeRelevancy: (suggestion) ->
     if suggestion.queryTerms.length
@@ -321,89 +354,226 @@ class TabCompleter
     else
       tabRecency.recencyScore(suggestion.tabId)
 
-# A completer which will return your search engines
 class SearchEngineCompleter
-  searchEngines: {}
-
-  filter: (queryTerms, onComplete) ->
-    {url: url, description: description} = @getSearchEngineMatches queryTerms
+  @debug: false
+  searchEngines: null
+
+  cancel: ->
+    CompletionSearch.cancel()
+
+  # This looks up the custom search engine and, if one is found, then notes it and removes its keyword from
+  # the query terms.  It also sets request.completers to indicate that only this completer should run.
+  triageRequest: (request) ->
+    @searchEngines.use (engines) =>
+      { queryTerms, query } = request
+      keyword = queryTerms[0]
+      if keyword and engines[keyword] and (1 < queryTerms.length or /\s$/.test query)
+        request.completers = [ this ]
+        extend request,
+          queryTerms: queryTerms[1..]
+          keyword: keyword
+          engine: engines[keyword]
+
+  refresh: (port) ->
+    # Parse the search-engine configuration.
+    @searchEngines = new AsyncDataFetcher (callback) ->
+      engines = {}
+      for line in Settings.get("searchEngines").split "\n"
+        line = line.trim()
+        continue if /^[#"]/.test line
+        tokens = line.split /\s+/
+        continue unless 2 <= tokens.length
+        keyword = tokens[0].split(":")[0]
+        url = tokens[1]
+        description = tokens[2..].join(" ") || "search (#{keyword})"
+        continue unless Utils.hasFullUrlPrefix url
+        engines[keyword] =
+          keyword: keyword
+          searchUrl: url
+          description: description
+
+      callback engines
+
+      # Let the front-end vomnibar know the search-engine keywords.
+      port.postMessage
+        handler: "keywords"
+        keywords: key for own key of engines
+
+  filter: ({ queryTerms, query, engine }, onComplete) ->
     suggestions = []
-    if url
-      url = url.replace(/%s/g, Utils.createSearchQuery queryTerms[1..])
-      if description
-        type = description
-        query = queryTerms[1..].join " "
-      else
-        type = "search"
-        query = queryTerms[0] + ": " + queryTerms[1..].join(" ")
-      suggestion = new Suggestion(queryTerms, type, url, query, @computeRelevancy)
-      suggestion.autoSelect = true
-      suggestions.push(suggestion)
-    onComplete(suggestions)
-
-  computeRelevancy: -> 1
 
-  refresh: ->
-    @searchEngines = SearchEngineCompleter.getSearchEngines()
-
-  getSearchEngineMatches: (queryTerms) ->
-    (1 < queryTerms.length and @searchEngines[queryTerms[0]]) or {}
-
-  # Static data and methods for parsing the configured search engines.  We keep a cache of the search-engine
-  # mapping in @searchEnginesMap.
-  @searchEnginesMap: null
-
-  # Parse the custom search engines setting and cache it in SearchEngineCompleter.searchEnginesMap.
-  @parseSearchEngines: (searchEnginesText) ->
-    searchEnginesMap = SearchEngineCompleter.searchEnginesMap = {}
-    for line in searchEnginesText.split /\n/
-      tokens = line.trim().split /\s+/
-      continue if tokens.length < 2 or tokens[0].startsWith('"') or tokens[0].startsWith("#")
-      keywords = tokens[0].split ":"
-      continue unless keywords.length == 2 and not keywords[1] # So, like: [ "w", "" ].
-      searchEnginesMap[keywords[0]] =
-        url: tokens[1]
-        description: tokens[2..].join(" ")
-
-  # Fetch the search-engine map, building it if necessary.
-  @getSearchEngines: ->
-    unless SearchEngineCompleter.searchEnginesMap?
-      SearchEngineCompleter.parseSearchEngines Settings.get "searchEngines"
-    SearchEngineCompleter.searchEnginesMap
+    { custom, searchUrl, description } =
+      if engine
+        { keyword, searchUrl, description } = engine
+        custom: true
+        searchUrl: searchUrl
+        description: description
+      else
+        custom: false
+        searchUrl: Settings.get "searchUrl"
+        description: "search"
+
+    return onComplete [] unless custom or 0 < queryTerms.length
+
+    query = queryTerms.join " "
+    factor = Settings.get "omniSearchWeight"
+    haveCompletionEngine = CompletionSearch.haveCompletionEngine searchUrl
+    haveCompletionEngine = false unless 0.0 < factor
+
+    # Relevancy:
+    #   - Relevancy does not depend upon the actual suggestion (so, it does not depend upon word
+    #     relevancy, say).  We assume that the completion engine has already factored that in.  Also,
+    #     completion engines often handle spelling mistakes, in which case we wouldn't find the query terms
+    #     in the suggestion anyway.
+    #   - Scores are weighted such that they retain the order provided by the completion engine.
+    #   - The relavancy is higher if the query term is longer.  The idea is that search suggestions are more
+    #     likely to be relevant if, after typing some number of characters, the user hasn't yet found
+    #     a useful suggestion from another completer.
+    #
+    characterCount = query.length - queryTerms.length + 1
+    relavancy = factor * (Math.min(characterCount, 10.0)/10.0)
+
+    # This distinguishes two very different kinds of vomnibar baviours, the newer bahviour (true) and the
+    # legacy behavior (false).  We retain the latter for the default search engine, and for custom search
+    # engines for which we do not have a completion engine.  By "exclusive vomnibar", we mean suggestions
+    # from other completers are suppressed (so the vomnibar "exclusively" uses suggestions from this search
+    # engine).
+    useExclusiveVomnibar = custom and haveCompletionEngine
+    filter = if useExclusiveVomnibar then (suggestion) -> suggestion.type == description else null
+
+    # For custom search engines, we add a single, top-ranked entry for the unmodified query.  This
+    # suggestion always appears at the top of the list.
+    if custom
+      suggestions.push new Suggestion
+        queryTerms: queryTerms
+        type: description
+        url: Utils.createSearchUrl queryTerms, searchUrl
+        title: query
+        relevancy: 1
+        insertText: if useExclusiveVomnibar then query else null
+        # We suppress the leading keyword, for example "w something" becomes "something" in the vomnibar.
+        suppressLeadingKeyword: true
+        selectCommonMatches: false
+        customSearchEnginePrimarySuggestion: true
+        # Toggles for the legacy behaviour.
+        autoSelect: not useExclusiveVomnibar
+        forceAutoSelect: not useExclusiveVomnibar
+        highlightTerms: not useExclusiveVomnibar
+
+    mkSuggestion = do ->
+      (suggestion) ->
+        new Suggestion
+          queryTerms: queryTerms
+          type: description
+          url: Utils.createSearchUrl suggestion, searchUrl
+          title: suggestion
+          relevancy: relavancy *= 0.9
+          insertText: suggestion
+          highlightTerms: false
+          selectCommonMatches: true
+          customSearchEngineCompletionSuggestion: true
+
+    # If we have cached suggestions, then we can bundle them immediately (otherwise we'll have to fetch them
+    # asynchronously).
+    cachedSuggestions = CompletionSearch.complete searchUrl, queryTerms
+
+    # Post suggestions and bail if we already have all of the suggestions, or if there is no prospect of
+    # adding further suggestions.
+    if queryTerms.length == 0 or cachedSuggestions? or not haveCompletionEngine
+      if cachedSuggestions? and 0 < factor
+        console.log "cached suggestions:", cachedSuggestions.length, query if SearchEngineCompleter.debug
+        suggestions.push cachedSuggestions.map(mkSuggestion)...
+      return onComplete suggestions, { filter, continuation: null }
+
+    # Post any initial suggestion, and then deliver the rest of the suggestions as a continuation (so,
+    # asynchronously).
+    onComplete suggestions,
+      filter: filter
+      continuation: (onComplete) =>
+        CompletionSearch.complete searchUrl, queryTerms, (suggestions = []) =>
+          console.log "fetched suggestions:", suggestions.length, query if SearchEngineCompleter.debug
+          onComplete suggestions.map mkSuggestion
 
 # A completer which calls filter() on many completers, aggregates the results, ranks them, and returns the top
 # 10. Queries from the vomnibar frontend script come through a multi completer.
 class MultiCompleter
-  constructor: (@completers) -> @maxResults = 10
+  maxResults: 10
 
-  refresh: -> completer.refresh() for completer in @completers when completer.refresh
+  constructor: (@completers) ->
+  refresh: (port) -> completer.refresh? port for completer in @completers
+  cancel: (port) -> completer.cancel? port for completer in @completers
 
-  filter: (queryTerms, onComplete) ->
+  filter: (request, onComplete) ->
     # Allow only one query to run at a time.
-    if @filterInProgress
-      @mostRecentQuery = { queryTerms: queryTerms, onComplete: onComplete }
-      return
+    return @mostRecentQuery = arguments if @filterInProgress
+
+    # Provide each completer with an opportunity to see (and possibly alter) the request before it is
+    # launched.  Each completer is also provided with a list of all of the completers we're using
+    # (request.completers), and may change that list to override the default (for example, the
+    # search-engine completer does this if it wants to be the *only* completer).
+    request.completers = @completers
+    completer.triageRequest? request for completer in @completers
+    completers = request.completers
+    delete request.completers
+
     RegexpCache.clear()
-    @mostRecentQuery = null
-    @filterInProgress = true
-    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)
-          @filterInProgress = false
-          @filter(@mostRecentQuery.queryTerms, @mostRecentQuery.onComplete) if @mostRecentQuery
-
-  sortSuggestions: (suggestions) ->
-    suggestion.computeRelevancy(@queryTerms) for suggestion in suggestions
+    { queryTerms } = request
+
+    [ @mostRecentQuery, @filterInProgress ] = [ null, true ]
+    [ suggestions, continuations, filters ] = [ [], [], [] ]
+
+    # Run each of the completers (asynchronously).
+    jobs = new JobRunner completers.map (completer) ->
+      (callback) ->
+        completer.filter request, (newSuggestions = [], { continuation, filter } = {}) ->
+          suggestions.push newSuggestions...
+          continuations.push continuation if continuation?
+          filters.push filter if filter?
+          callback()
+
+    # Once all completers have finished, process the results and post them, and run any continuations or
+    # pending queries.
+    jobs.onReady =>
+      suggestions = suggestions.filter filter for filter in filters
+      shouldRunContinuations = 0 < continuations.length and not @mostRecentQuery?
+
+      # Post results, unless there are none and we will be running a continuation.  This avoids
+      # collapsing the vomnibar briefly before expanding it again, which looks ugly.
+      unless suggestions.length == 0 and shouldRunContinuations
+        suggestions = @prepareSuggestions queryTerms, suggestions
+        onComplete
+          results: suggestions
+          mayCacheResults: continuations.length == 0
+
+      # Run any continuations (asynchronously); for example, the search-engine completer
+      # (SearchEngineCompleter) uses a continuation to fetch suggestions from completion engines
+      # asynchronously.
+      if shouldRunContinuations
+        jobs = new JobRunner continuations.map (continuation) ->
+          (callback) ->
+            continuation (newSuggestions) ->
+              suggestions.push newSuggestions...
+              callback()
+
+        jobs.onReady =>
+          suggestions = @prepareSuggestions queryTerms, suggestions
+          # We post these results even if a new query has started.  The vomnibar will not display them
+          # (because they're arriving too late), but it will cache them.
+          onComplete
+            results: suggestions
+            mayCacheResults: true
+
+      # Admit subsequent queries, and launch any pending query.
+      @filterInProgress = false
+      if @mostRecentQuery
+        @filter @mostRecentQuery...
+
+  prepareSuggestions: (queryTerms, suggestions) ->
+    suggestion.computeRelevancy queryTerms for suggestion in suggestions
     suggestions.sort (a, b) -> b.relevancy - a.relevancy
-    suggestions
+    for suggestion in suggestions[0...@maxResults]
+      suggestion.generateHtml()
+      suggestion
 
 # Utilities which help us compute a relevancy score for a given item.
 RankingUtils =
@@ -551,8 +721,7 @@ HistoryCache =
     @callbacks = null
 
   use: (callback) ->
-    return @fetchHistory(callback) unless @history?
-    callback(@history)
+    if @history? then callback @history else @fetchHistory callback
 
   fetchHistory: (callback) ->
     return @callbacks.push(callback) if @callbacks
diff --git a/background_scripts/completion_engines.coffee b/background_scripts/completion_engines.coffee
new file mode 100644
index 00000000..14e65692
--- /dev/null
+++ b/background_scripts/completion_engines.coffee
@@ -0,0 +1,120 @@
+
+# A completion engine provides search suggestions for a search engine.  A search engine is identified by a
+# "searchUrl", e.g. Settings.get("searchUrl"), or a custom search engine.
+#
+# Each completion engine defines three functions:
+#
+#   1. "match" - This takes a searchUrl and returns a boolean indicating whether this completion engine can
+#      perform completion for the given search engine.
+#
+#   2. "getUrl" - This takes a list of query terms (queryTerms) and generates a completion URL, that is, a URL
+#      which will provide completions for this completion engine.
+#
+#   3. "parse" - This takes a successful XMLHttpRequest object (the request has completed successfully), and
+#      returns a list of suggestions (a list of strings).  This method is always executed within the context
+#      of a try/catch block, so errors do not propagate.
+#
+# Each new completion engine must be add to the list "CompletionEngines" at the bottom of this file.
+#
+# The lookup logic which uses these completion engines is in "./completion_search.coffee".
+#
+
+# A base class for common regexp-based matching engines.
+class RegexpEngine
+  constructor: (@regexps) ->
+  match: (searchUrl) -> Utils.matchesAnyRegexp @regexps, searchUrl
+
+# Several Google completion engines package XML responses in this way.
+class GoogleXMLRegexpEngine extends RegexpEngine
+  doNotCache: false # true (disbaled, experimental)
+  parse: (xhr) ->
+    for suggestion in xhr.responseXML.getElementsByTagName "suggestion"
+      continue unless suggestion = suggestion.getAttribute "data"
+      suggestion
+
+class Google extends GoogleXMLRegexpEngine
+  # Example search URL: http://www.google.com/search?q=%s
+  constructor: ->
+    super [
+      # We match the major English-speaking TLDs.
+      new RegExp "^https?://[a-z]+\.google\.(com|ie|co\.uk|ca|com\.au)/"
+      new RegExp "localhost/cgi-bin/booky" # Only for smblott.
+      ]
+
+  getUrl: (queryTerms) ->
+    "http://suggestqueries.google.com/complete/search?ss_protocol=legace&client=toolbar&q=#{Utils.createSearchQuery queryTerms}"
+
+class Youtube extends GoogleXMLRegexpEngine
+  # Example search URL: http://www.youtube.com/results?search_query=%s
+  constructor: ->
+    super [ new RegExp "^https?://[a-z]+\.youtube\.com/results" ]
+
+  getUrl: (queryTerms) ->
+    "http://suggestqueries.google.com/complete/search?client=youtube&ds=yt&xml=t&q=#{Utils.createSearchQuery queryTerms}"
+
+class Wikipedia extends RegexpEngine
+  doNotCache: false # true (disbaled, experimental)
+  # Example search URL: http://www.wikipedia.org/w/index.php?title=Special:Search&search=%s
+  constructor: ->
+    super [ new RegExp "^https?://[a-z]+\.wikipedia\.org/" ]
+
+  getUrl: (queryTerms) ->
+    "https://en.wikipedia.org/w/api.php?action=opensearch&format=json&search=#{Utils.createSearchQuery queryTerms}"
+
+  parse: (xhr) ->
+    JSON.parse(xhr.responseText)[1]
+
+## Does not work...
+## class GoogleMaps extends RegexpEngine
+##   # Example search URL: https://www.google.com/maps/search/%s
+##   constructor: ->
+##     super [ new RegExp "^https?://www\.google\.com/maps/search/" ]
+##
+##   getUrl: (queryTerms) ->
+##     "https://www.google.com/s?tbm=map&fp=1&gs_ri=maps&source=hp&suggest=p&authuser=0&hl=en&pf=p&tch=1&ech=2&q=#{Utils.createSearchQuery queryTerms}"
+##
+##   parse: (xhr) ->
+##     data = JSON.parse xhr.responseText
+##     []
+
+class Bing extends RegexpEngine
+  # Example search URL: https://www.bing.com/search?q=%s
+  constructor: -> super [ new RegExp "^https?://www\.bing\.com/search" ]
+  getUrl: (queryTerms) -> "http://api.bing.com/osjson.aspx?query=#{Utils.createSearchQuery queryTerms}"
+  parse: (xhr) -> JSON.parse(xhr.responseText)[1]
+
+class Amazon extends RegexpEngine
+  # Example search URL: http://www.amazon.com/s/?field-keywords=%s
+  constructor: -> super [ new RegExp "^https?://www\.amazon\.(com|co.uk|ca|com.au)/s/" ]
+  getUrl: (queryTerms) -> "https://completion.amazon.com/search/complete?method=completion&search-alias=aps&client=amazon-search-ui&mkt=1&q=#{Utils.createSearchQuery queryTerms}"
+  parse: (xhr) -> JSON.parse(xhr.responseText)[1]
+
+class DuckDuckGo extends RegexpEngine
+  # Example search URL: https://duckduckgo.com/?q=%s
+  constructor: -> super [ new RegExp "^https?://([a-z]+\.)?duckduckgo\.com/" ]
+  getUrl: (queryTerms) -> "https://duckduckgo.com/ac/?q=#{Utils.createSearchQuery queryTerms}"
+  parse: (xhr) ->
+    suggestion.phrase for suggestion in JSON.parse xhr.responseText
+
+# A dummy search engine which is guaranteed to match any search URL, but never produces completions.  This
+# allows the rest of the logic to be written knowing that there will always be a completion engine match.
+class DummyCompletionEngine
+  dummy: true
+  match: -> true
+  # We return a useless URL which we know will succeed, but which won't generate any network traffic.
+  getUrl: -> chrome.runtime.getURL "content_scripts/vimium.css"
+  parse: -> []
+
+# Note: Order matters here.
+CompletionEngines = [
+  Youtube
+  Google
+  DuckDuckGo
+  Wikipedia
+  Bing
+  Amazon
+  DummyCompletionEngine
+]
+
+root = exports ? window
+root.CompletionEngines = CompletionEngines
diff --git a/background_scripts/completion_search.coffee b/background_scripts/completion_search.coffee
new file mode 100644
index 00000000..2d2ee439
--- /dev/null
+++ b/background_scripts/completion_search.coffee
@@ -0,0 +1,133 @@
+
+CompletionSearch =
+  debug: false
+  inTransit: {}
+  completionCache: new SimpleCache 2 * 60 * 60 * 1000, 5000 # Two hour, 5000 entries.
+  engineCache:new SimpleCache 1000 * 60 * 60 * 1000 # 1000 hours.
+
+  # The amount of time to wait for new requests before launching the current request (for example, if the user
+  # is still typing).
+  delay: 100
+
+  get: (searchUrl, url, callback) ->
+    xhr = new XMLHttpRequest()
+    xhr.open "GET", url, true
+    xhr.timeout = 1000
+    xhr.ontimeout = xhr.onerror = -> callback null
+    xhr.send()
+
+    xhr.onreadystatechange = ->
+      if xhr.readyState == 4
+        callback if xhr.status == 200 then xhr else null
+
+  # Look up the completion engine for this searchUrl.  Because of DummyCompletionEngine, we know there will
+  # always be a match.
+  lookupEngine: (searchUrl) ->
+    if @engineCache.has searchUrl
+      @engineCache.get searchUrl
+    else
+      for engine in CompletionEngines
+        engine = new engine()
+        return @engineCache.set searchUrl, engine if engine.match searchUrl
+
+  # True if we have a completion engine for this search URL, false otherwise.
+  haveCompletionEngine: (searchUrl) ->
+    not @lookupEngine(searchUrl).dummy
+
+  # This is the main entry point.
+  #  - searchUrl is the search engine's URL, e.g. Settings.get("searchUrl"), or a custome search engine's URL.
+  #    This is only used as a key for determining the relevant completion engine.
+  #  - queryTerms are the query terms.
+  #  - callback will be applied to a list of suggestion strings (which may be an empty list, if anything goes
+  #    wrong).
+  #
+  # If no callback is provided, then we're to provide suggestions only if we can do so synchronously (ie.
+  # from a cache).  In this case we just return the results.  Returns null if we cannot service the request
+  # synchronously.
+  #
+  complete: (searchUrl, queryTerms, callback = null) ->
+    query = queryTerms.join(" ").toLowerCase()
+
+    returnResultsOnlyFromCache = not callback?
+    callback ?= (suggestions) -> suggestions
+
+    # We don't complete queries which are too short: the results are usually useless.
+    return callback [] unless 3 < query.length
+
+    # We don't complete regular URLs or Javascript URLs.
+    return callback [] if 1 == queryTerms.length and Utils.isUrl query
+    return callback [] if Utils.hasJavascriptPrefix query
+
+    # Cache completions.  However, completions depend upon both the searchUrl and the query terms.  So we need
+    # to generate a key.  We mix in some junk generated by pwgen. A key clash might be possible, but
+    # is vanishingly unlikely.
+    junk = "//Zi?ei5;o//"
+    completionCacheKey = searchUrl + junk + queryTerms.map((s) -> s.toLowerCase()).join junk
+
+    if @completionCache.has completionCacheKey
+      console.log "hit", completionCacheKey if @debug
+      return callback @completionCache.get completionCacheKey
+
+    # If the user appears to be typing a continuation of the characters of the most recent query, then we can
+    # re-use the previous suggestions.
+    if @mostRecentQuery? and @mostRecentSuggestions?
+      reusePreviousSuggestions = do =>
+        # Verify that the previous query is a prefix of the current query.
+        return false unless 0 == query.indexOf @mostRecentQuery.toLowerCase()
+        # Verify that every previous suggestion contains the text of the new query.
+        for suggestion in (@mostRecentSuggestions.map (s) -> s.toLowerCase())
+          return false unless 0 <= suggestion.indexOf query
+        # Ok. Re-use the suggestion.
+        true
+
+      if reusePreviousSuggestions
+        console.log "reuse previous query:", @mostRecentQuery if @debug
+        @mostRecentQuery = queryTerms.join " "
+        return callback @completionCache.set completionCacheKey, @mostRecentSuggestions
+
+    # That's all of the caches we can try.  Bail if the caller is looking for synchronous results.
+    return callback null if returnResultsOnlyFromCache
+
+    # We pause in case the user is still typing.
+    Utils.setTimeout @delay, handler = @mostRecentHandler = =>
+      if handler == @mostRecentHandler
+        @mostRecentHandler = null
+
+        # Elide duplicate requests. First fetch the suggestions...
+        @inTransit[completionCacheKey] ?= new AsyncDataFetcher (callback) =>
+          engine = @lookupEngine searchUrl
+          url = engine.getUrl queryTerms
+
+          @get searchUrl, url, (xhr = null) =>
+            # Parsing the response may fail if we receive an unexpected or an unexpectedly-formatted response.
+            # In all cases, we fall back to the catch clause, below.  Therefore, we "fail safe" in the case of
+            # incorrect or out-of-date completion engines.
+            try
+              suggestions = engine.parse xhr
+              # Filter out the query itself. It's not adding anything.
+              suggestions = (suggestion for suggestion in suggestions when suggestion.toLowerCase() != query)
+              console.log "GET", url if @debug
+            catch
+              suggestions = []
+              # We allow failures to be cached too, but remove them after just thirty minutes.
+              Utils.setTimeout 30 * 60 * 1000, => @completionCache.set completionCacheKey, null
+              console.log "fail", url if @debug
+
+            callback suggestions
+
+        # ... then use the suggestions.
+        @inTransit[completionCacheKey].use (suggestions) =>
+          @mostRecentQuery = query
+          @mostRecentSuggestions = suggestions
+          callback @completionCache.set completionCacheKey, suggestions
+          delete @inTransit[completionCacheKey]
+
+  # Cancel any pending (ie. blocked on @delay) queries.  Does not cancel in-flight queries.  This is called
+  # whenever the user is typing.
+  cancel: ->
+    if @mostRecentHandler?
+      @mostRecentHandler = null
+      console.log "cancel (user is typing)" if @debug
+
+root = exports ? window
+root.CompletionSearch = CompletionSearch
diff --git a/background_scripts/main.coffee b/background_scripts/main.coffee
index dc87ac54..913f1de5 100644
--- a/background_scripts/main.coffee
+++ b/background_scripts/main.coffee
@@ -43,20 +43,36 @@ chrome.storage.local.set
   vimiumSecret: Math.floor Math.random() * 2000000000
 
 completionSources =
-  bookmarks: new BookmarkCompleter()
-  history: new HistoryCompleter()
-  domains: new DomainCompleter()
-  tabs: new TabCompleter()
-  seachEngines: new SearchEngineCompleter()
+  bookmarks: new BookmarkCompleter
+  history: new HistoryCompleter
+  domains: new DomainCompleter
+  tabs: new TabCompleter
+  searchEngines: new SearchEngineCompleter
 
 completers =
-  omni: new MultiCompleter([
-    completionSources.seachEngines,
-    completionSources.bookmarks,
-    completionSources.history,
-    completionSources.domains])
-  bookmarks: new MultiCompleter([completionSources.bookmarks])
-  tabs: new MultiCompleter([completionSources.tabs])
+  omni: new MultiCompleter [
+    completionSources.bookmarks
+    completionSources.history
+    completionSources.domains
+    completionSources.searchEngines
+    ]
+  bookmarks: new MultiCompleter [completionSources.bookmarks]
+  tabs: new MultiCompleter [completionSources.tabs]
+
+completionHandlers =
+  filter: (completer, request, port) ->
+    completer.filter request, (response) ->
+      # We use try here because this may fail if the sender has already navigated away from the original page.
+      # This can happen, for example, when posting completion suggestions from the SearchEngineCompleter
+      # (which can be slow).
+      try
+        port.postMessage extend request, extend response, handler: "completions"
+
+  refresh: (completer, _, port) -> completer.refresh port
+  cancel: (completer, _, port) -> completer.cancel port
+
+handleCompletions = (request, port) ->
+  completionHandlers[request.handler] completers[request.name], request, port
 
 chrome.runtime.onConnect.addListener (port, name) ->
   senderTabId = if port.sender.tab then port.sender.tab.id else null
@@ -215,13 +231,6 @@ handleSettings = (request, port) ->
       values[key] = Settings.get key for own key of values
       port.postMessage { values }
 
-refreshCompleter = (request) -> completers[request.name].refresh()
-
-whitespaceRegexp = /\s+/
-filterCompleter = (args, port) ->
-  queryTerms = if (args.query == "") then [] else args.query.split(whitespaceRegexp)
-  completers[args.name].filter(queryTerms, (results) -> port.postMessage({ id: args.id, results: results }))
-
 chrome.tabs.onSelectionChanged.addListener (tabId, selectionInfo) ->
   if (selectionChangedHandlers.length > 0)
     selectionChangedHandlers.pop().call()
@@ -640,7 +649,7 @@ bgLog = (request, sender) ->
 portHandlers =
   keyDown: handleKeyDown,
   settings: handleSettings,
-  filterCompleter: filterCompleter
+  completions: handleCompletions
 
 sendRequestHandlers =
   getCompletionKeys: getCompletionKeysRequest
@@ -658,7 +667,6 @@ sendRequestHandlers =
   pasteFromClipboard: pasteFromClipboard
   isEnabledForUrl: isEnabledForUrl
   selectSpecificTab: selectSpecificTab
-  refreshCompleter: refreshCompleter
   createMark: Marks.create.bind(Marks)
   gotoMark: Marks.goto.bind(Marks)
   setIcon: setIcon
diff --git a/background_scripts/settings.coffee b/background_scripts/settings.coffee
index 1077c84c..afc270fd 100644
--- a/background_scripts/settings.coffee
+++ b/background_scripts/settings.coffee
@@ -32,9 +32,6 @@ root.Settings = Settings =
       root.Commands.parseCustomKeyMappings value
       root.refreshCompletionKeysAfterMappingSave()
 
-    searchEngines: (value) ->
-      root.SearchEngineCompleter.parseSearchEngines value
-
     exclusionRules: (value) ->
       root.Exclusions.postUpdateHook value
 
@@ -46,6 +43,7 @@ root.Settings = Settings =
   # or strings
   defaults:
     scrollStepSize: 60
+    omniSearchWeight: 0.6
     smoothScroll: true
     keyMappings: "# Insert your preferred key mappings here."
     linkHintCharacters: "sadfjklewcmpgh"
@@ -90,7 +88,24 @@ root.Settings = Settings =
     # default/fall back search engine
     searchUrl: "https://www.google.com/search?q="
     # put in an example search engine
-    searchEngines: "w: http://www.wikipedia.org/w/index.php?title=Special:Search&search=%s wikipedia"
+    searchEngines: [
+      "w: http://www.wikipedia.org/w/index.php?title=Special:Search&search=%s Wikipedia"
+      ""
+      "# More examples."
+      "#"
+      "# (Vimium has built-in completion for these.)"
+      "#"
+      "# g: http://www.google.com/search?q=%s Google"
+      "# l: http://www.google.com/search?q=%s&btnI I'm feeling lucky..."
+      "# y: http://www.youtube.com/results?search_query=%s Youtube"
+      "# b: https://www.bing.com/search?q=%s Bing"
+      "# d: https://duckduckgo.com/?q=%s DuckDuckGo"
+      "# az: http://www.amazon.com/s/?field-keywords=%s Amazon"
+      "#"
+      "# Another example (for Vimium does not have completion)."
+      "#"
+      "# m: https://www.google.com/maps/search/%s Google Maps"
+      ].join "\n"
     newTabUrl: "chrome://newtab"
     grabBackFocus: false