diff options
| -rw-r--r-- | background_scripts/completion.coffee | 45 | ||||
| -rw-r--r-- | lib/utils.coffee | 8 | ||||
| -rw-r--r-- | tests/unit_tests/completion_test.coffee | 53 |
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 = [] |