Factor pushMatchingRanges, improve comments/tests

1. Factor out `pushMatchingRanges`:
   This then allows us to ...
2. Add unit tests for `pushMatchingRanges`
   In effect, these tests verify where matches are highlighted in suggestions.
3. Added Utils.zip.  This helps simplify `pushMatchingRanges` unit tests.
4. Improve comments.

3 files changed, 66 insertions, 12 deletions

diff --git a/background_scripts/completion.coffee b/background_scripts/completion.coffee
index c8a06b27..ab24377a 100644
--- a/background_scripts/completion.coffee
+++ b/background_scripts/completion.coffee
@@ -46,19 +46,32 @@ 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:
+    #   - splits[i%2] is unmatched text
+    #   - splits[(i%2)+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
-      textPosition = 0
-      splits = string.split(RegexpCache.get(term, "(", ")")).reverse()
-      while 0 < splits.length
-        unmatchedText = splits.pop()
-        textPosition += unmatchedText.length
-        matchedText = if 0 < splits.length then splits.pop() else null
-        if matchedText
-          ranges.push([textPosition, textPosition + matchedText.length])
-          textPosition += matchedText.length
+      @pushMatchingRanges string, term, ranges
 
     return string if ranges.length == 0
 
@@ -314,9 +327,14 @@ RegexpCache =
 
   clear: -> @cache = {}
 
-  # Get rexexp for string from cache, creating the regexp if necessary.
-  # Regexp meta-characters in string are escaped.
-  # Regexp is wrapped in prefix/suffix, which may contain meta-characters.
+  # 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
     regexpString = string.replace(@escapeRegExp, "\\$&")
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 f978c57b..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")