Merge pull request #704 from smblott-github/relevancy

Highlight all matches in a vomnibar suggestion, not just the first.

3 files changed, 99 insertions, 7 deletions

diff --git a/background_scripts/completion.coffee b/background_scripts/completion.coffee
index e959d358..25f76c1e 100644
--- a/background_scripts/completion.coffee
+++ b/background_scripts/completion.coffee
@@ -46,12 +46,33 @@ class Suggestion
     url = url.substring(url, url.length - 1) if url[url.length - 1] == "/"
     url
 
+  # Push the ranges within `string` which match `term` onto `ranges`.
+  pushMatchingRanges: (string,term,ranges) ->
+    textPosition = 0
+    # Split `string` into a (flat) list of pairs:
+    #   - for i=0,2,4,6,...
+    #     - splits[i] is unmatched text
+    #     - splits[i+1] is the following matched text (matching `term`)
+    #       (except for the final element, for which there is no following matched text).
+    # Example:
+    #   - string = "Abacab"
+    #   - term = "a"
+    #   - splits = [ "", "A",    "b", "a",    "c", "a",    b" ]
+    #                UM   M       UM   M       UM   M      UM      (M=Matched, UM=Unmatched)
+    splits = string.split(RegexpCache.get(term, "(", ")"))
+    for index in [0..splits.length-2] by 2
+      unmatchedText = splits[index]
+      matchedText = splits[index+1]
+      # Add the indices spanning `matchedText` to `ranges`.
+      textPosition += unmatchedText.length
+      ranges.push([textPosition, textPosition + matchedText.length])
+      textPosition += matchedText.length
+
   # Wraps each occurence of the query terms in the given string in a <span>.
   highlightTerms: (string) ->
     ranges = []
     for term in @queryTerms
-      i = string.search(RegexpCache.get(term))
-      ranges.push([i, i + term.length]) if i >= 0
+      @pushMatchingRanges string, term, ranges
 
     return string if ranges.length == 0
 
@@ -307,12 +328,21 @@ RegexpCache =
 
   clear: -> @cache = {}
 
-  get: (string) ->
+  # Get rexexp for `string` from cache, creating it if necessary.
+  # Regexp meta-characters in `string` are escaped.
+  # Regexp is wrapped in `prefix`/`suffix`, which may contain meta-characters (these are not escaped).
+  # With their default values, `prefix` and `suffix` have no effect.
+  # Example:
+  #   - string="go", prefix="\b", suffix=""
+  #   - this returns regexp matching "google", but not "agog" (the "go" must occur at the start of a word)
+  # TODO: `prefix` and `suffix` might be useful in richer word-relevancy scoring.
+  get: (string, prefix="", suffix="") ->
     @init() unless @initialized
-    @cache[string] ||= @escapeRegexp(string)
-
-  # Creates a Regexp from the given string, with all special Regexp characters escaped.
-  escapeRegexp: (string) -> new RegExp(string.replace(@escapeRegExp, "\\$&"), "i")
+    regexpString = string.replace(@escapeRegExp, "\\$&")
+    # Avoid cost of constructing new strings if prefix/suffix are empty (which is expected to be a common case).
+    regexpString = prefix + regexpString if prefix
+    regexpString = regexpString + suffix if suffix
+    @cache[regexpString] ||= new RegExp(regexpString, "i")
 
 # Provides cached access to Chrome's history. As the user browses to new pages, we add those pages to this
 # history cache.
@@ -382,3 +412,4 @@ root.DomainCompleter = DomainCompleter
 root.TabCompleter = TabCompleter
 root.HistoryCache = HistoryCache
 root.RankingUtils = RankingUtils
+root.RegexpCache = RegexpCache
diff --git a/lib/utils.coffee b/lib/utils.coffee
index e89d0aa2..c997b74b 100644
--- a/lib/utils.coffee
+++ b/lib/utils.coffee
@@ -126,6 +126,14 @@ Utils =
         return 1
     0
 
+  # Zip two (or more) arrays:
+  #   - Utils.zip([ [a,b], [1,2] ]) returns [ [a,1], [b,2] ]
+  #   - Length of result is `arrays[0].length`.
+  #   - Adapted from: http://stackoverflow.com/questions/4856717/javascript-equivalent-of-pythons-zip-function
+  zip: (arrays) ->
+    arrays[0].map (_,i) ->
+      arrays.map( (array) -> array[i] )
+    
 # This creates a new function out of an existing function, where the new function takes fewer arguments. This
 # allows us to pass around functions instead of functions + a partial list of arguments.
 Function::curry = ->
diff --git a/tests/unit_tests/completion_test.coffee b/tests/unit_tests/completion_test.coffee
index 32b62a28..3de1d716 100644
--- a/tests/unit_tests/completion_test.coffee
+++ b/tests/unit_tests/completion_test.coffee
@@ -152,6 +152,34 @@ context "suggestions",
     suggestion = new Suggestion(["queryterm"], "tab", "http://ninjawords.com", "ninjawords", returns(1))
     assert.equal -1, suggestion.generateHtml().indexOf("http://ninjawords.com")
 
+  should "extract ranges matching term (simple case, two matches)", ->
+    ranges = []
+    [ one, two, three ] = [ "one", "two", "three" ]
+    suggestion = new Suggestion([], "", "", "", returns(1))
+    suggestion.pushMatchingRanges("#{one}#{two}#{three}#{two}#{one}", two, ranges)
+    assert.equal 2, Utils.zip([ ranges, [ [3,6], [11,14] ] ]).filter((pair) -> pair[0][0] == pair[1][0] and pair[0][1] == pair[1][1]).length
+
+  should "extract ranges matching term (two matches, one at start of string)", ->
+    ranges = []
+    [ one, two, three ] = [ "one", "two", "three" ]
+    suggestion = new Suggestion([], "", "", "", returns(1))
+    suggestion.pushMatchingRanges("#{two}#{three}#{two}#{one}", two, ranges)
+    assert.equal 2, Utils.zip([ ranges, [ [0,3], [8,11] ] ]).filter((pair) -> pair[0][0] == pair[1][0] and pair[0][1] == pair[1][1]).length
+
+  should "extract ranges matching term (two matches, one at end of string)", ->
+    ranges = []
+    [ one, two, three ] = [ "one", "two", "three" ]
+    suggestion = new Suggestion([], "", "", "", returns(1))
+    suggestion.pushMatchingRanges("#{one}#{two}#{three}#{two}", two, ranges)
+    assert.equal 2, Utils.zip([ ranges, [ [3,6], [11,14] ] ]).filter((pair) -> pair[0][0] == pair[1][0] and pair[0][1] == pair[1][1]).length
+
+  should "extract ranges matching term (no matches)", ->
+    ranges = []
+    [ one, two, three ] = [ "one", "two", "three" ]
+    suggestion = new Suggestion([], "", "", "", returns(1))
+    suggestion.pushMatchingRanges("#{one}#{two}#{three}#{two}#{one}", "does-not-match", ranges)
+    assert.equal 0, ranges.length
+
 context "RankingUtils",
   should "do a case insensitive match", ->
     assert.isTrue RankingUtils.matches(["aRi"], "MARIO", "MARio")
@@ -174,6 +202,31 @@ context "RankingUtils",
   should "every term must match at least one thing (not matching)", ->
     assert.isTrue not RankingUtils.matches(["cat", "dog", "wolf"], "catapult", "hound dog")
 
+context "RegexpCache",
+  should "RegexpCache is in fact caching (positive case)", ->
+    assert.isTrue RegexpCache.get("this") is RegexpCache.get("this")
+
+  should "RegexpCache is in fact caching (negative case)", ->
+    assert.isTrue RegexpCache.get("this") isnt RegexpCache.get("that")
+
+  should "RegexpCache prefix/suffix wrapping is working (positive case)", ->
+    assert.isTrue RegexpCache.get("this", "(", ")") is RegexpCache.get("this", "(", ")")
+
+  should "RegexpCache prefix/suffix wrapping is working (negative case)", ->
+    assert.isTrue RegexpCache.get("this", "(", ")") isnt RegexpCache.get("this")
+
+  should "search for a string", ->
+    assert.isTrue "hound dog".search(RegexpCache.get("dog")) == 6
+
+  should "search for a string which isn't there", ->
+    assert.isTrue "hound dog".search(RegexpCache.get("cat")) == -1
+
+  should "search for a string with a prefix/suffix (positive case)", ->
+    assert.isTrue "hound dog".search(RegexpCache.get("dog", "\\b", "\\b")) == 6
+
+  should "search for a string with a prefix/suffix (negative case)", ->
+    assert.isTrue "hound dog".search(RegexpCache.get("do", "\\b", "\\b")) == -1
+
 # A convenience wrapper around completer.filter() so it can be called synchronously in tests.
 filterCompleter = (completer, queryTerms) ->
   results = []