From e97119ae720b3028499b65833066cd048e3b0257 Mon Sep 17 00:00:00 2001 From: Simon Lydell Date: Fri, 23 Jan 2015 21:21:52 +0100 Subject: [PATCH] Remove bloomfilter The bloomfilter can run out of space, and actually does so pretty quickly: See #176. When it is full it is not of any help anymore. All it does then is unconditionally giving better hints to `` elements. But since commit 01657421 that is done in a better way. In summary, the bloomfilter is not useful anymore. --- extension/defaults/preferences/defaults.js | 2 - extension/lib/mode-hints/bloomfilter.coffee | 163 -------------------- extension/lib/mode-hints/hints.coffee | 7 +- extension/lib/mode-hints/marker.coffee | 58 +------ extension/lib/mode-hints/mode-hints.coffee | 1 - extension/locale/de/options.dtd | 3 - extension/locale/el-GR/options.dtd | 3 - extension/locale/en-US/options.dtd | 3 - extension/locale/hu/options.dtd | 3 - extension/locale/id/options.dtd | 3 - extension/locale/it/options.dtd | 3 - extension/locale/ja/options.dtd | 3 - extension/locale/nl/options.dtd | 3 - extension/locale/pl/options.dtd | 3 - extension/locale/ru/options.dtd | 3 - extension/locale/sv-SE/options.dtd | 3 - extension/locale/zh-CN/options.dtd | 3 - extension/locale/zh-TW/options.dtd | 3 - extension/options.xul | 2 - 19 files changed, 4 insertions(+), 268 deletions(-) delete mode 100644 extension/lib/mode-hints/bloomfilter.coffee diff --git a/extension/defaults/preferences/defaults.js b/extension/defaults/preferences/defaults.js index 23a7c0b..3c10db5 100644 --- a/extension/defaults/preferences/defaults.js +++ b/extension/defaults/preferences/defaults.js @@ -3,9 +3,7 @@ pref('extensions.VimFx.prev_patterns', 'prev,previous,‹,«,◀,←,<< pref('extensions.VimFx.next_patterns', 'next,›,»,▶,→,>>,>,more,older'); pref('extensions.VimFx.scroll_step_lines', 6); pref('extensions.VimFx.black_list', '*example.com*'); -pref('extensions.VimFx.hints_bloom_data', ''); pref('extensions.VimFx.prevent_autofocus', true); pref('extensions.VimFx.autofocus_limit', 100); -pref('extensions.VimFx.hints_bloom_on', true); pref('extensions.VimFx.ignore_keyboard_layout', false); pref('extensions.VimFx.translations', '{}'); diff --git a/extension/lib/mode-hints/bloomfilter.coffee b/extension/lib/mode-hints/bloomfilter.coffee deleted file mode 100644 index ab7ae4b..0000000 --- a/extension/lib/mode-hints/bloomfilter.coffee +++ /dev/null @@ -1,163 +0,0 @@ -# coffeelint: disable=max_line_length -# coffeelint: disable=no_backticks - -{ getPref -, setPref } = require('../prefs') - -` -(function(exports) { - exports.BloomFilter = BloomFilter; - exports.fnv_1a = fnv_1a; - exports.fnv_1a_b = fnv_1a_b; - - var typedArrays = typeof ArrayBuffer !== "undefined"; - - // Creates a new bloom filter. If *m* is an array-like object, with a length - // property, then the bloom filter is loaded with data from the array, where - // each element is a 32-bit integer. Otherwise, *m* should specify the - // number of bits. *k* specifies the number of hashing functions. - function BloomFilter(m, k) { - var a; - if (typeof m !== "number") a = m, m = a.length * 32; - - this.m = m; - this.k = k; - var n = Math.ceil(m / 32), - i = -1; - - if (typedArrays) { - var kbytes = 1 << Math.ceil(Math.log(Math.ceil(Math.log(m) / Math.LN2 / 8)) / Math.LN2), - array = kbytes === 1 ? Uint8Array : kbytes === 2 ? Uint16Array : Uint32Array, - kbuffer = new ArrayBuffer(kbytes * k), - buckets = this.buckets = new Int32Array(n); - if (a) while (++i < n) buckets[i] = a[i]; - this._locations = new array(kbuffer); - } else { - var buckets = this.buckets = []; - if (a) while (++i < n) buckets[i] = a[i]; - else while (++i < n) buckets[i] = 0; - this._locations = []; - } - } - - // See http://willwhim.wordpress.com/2011/09/03/producing-n-hash-functions-by-hashing-only-once/ - BloomFilter.prototype.locations = function(v) { - var k = this.k, - m = this.m, - r = this._locations, - a = fnv_1a(v), - b = fnv_1a_b(a), - i = -1, - x = a % m; - while (++i < k) { - r[i] = x < 0 ? (x + m) : x; - x = (x + b) % m; - } - return r; - }; - - BloomFilter.prototype.add = function(v) { - var l = this.locations(v + ""), - i = -1, - k = this.k, - buckets = this.buckets; - while (++i < k) buckets[Math.floor(l[i] / 32)] |= 1 << (l[i] % 32); - }; - - BloomFilter.prototype.test = function(v) { - var l = this.locations(v + ""), - i = -1, - k = this.k, - b, - buckets = this.buckets; - while (++i < k) { - b = l[i]; - if ((buckets[Math.floor(b / 32)] & (1 << (b % 32))) === 0) { - return false; - } - } - return true; - }; - - // Estimated cardinality. - BloomFilter.prototype.size = function() { - var buckets = this.buckets, - bits = 0; - for (var i = 0, n = buckets.length; i < n; ++i) bits += popcnt(buckets[i]); - return -this.m * Math.log(1 - bits / this.m) / this.k; - }; - - // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel - function popcnt(v) { - v -= (v >> 1) & 0x55555555; - v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; - } - - // Fowler/Noll/Vo hashing. - function fnv_1a(v) { - var n = v.length, - a = 2166136261, - c, - d, - i = -1; - while (++i < n) { - c = v.charCodeAt(i); - if (d = c & 0xff000000) { - a ^= d >> 24; - a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24); - } - if (d = c & 0xff0000) { - a ^= d >> 16; - a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24); - } - if (d = c & 0xff00) { - a ^= d >> 8; - a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24); - } - a ^= c & 0xff; - a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24); - } - // From http://home.comcast.net/~bretm/hash/6.html - a += a << 13; - a ^= a >> 7; - a += a << 3; - a ^= a >> 17; - a += a << 5; - return a & 0xffffffff; - } - - // One additional iteration of FNV, given a hash. - function fnv_1a_b(a) { - a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24); - a += a << 13; - a ^= a >> 7; - a += a << 3; - a ^= a >> 17; - a += a << 5; - return a & 0xffffffff; - } -})(typeof exports !== "undefined" ? exports : this); -` - -class DummyBloomFilter - save: -> - add: -> - test: -> - size: -> - popcnt: -> - -class SerializableBloomFilter extends exports.BloomFilter - constructor: (@prefName, m, k) -> - if data = getPref(@prefName) - super(JSON.parse(data), k) - else - super(m, k) - - save: -> - data = JSON.stringify([].slice.call(@buckets)) - setPref(@prefName, data) - - -exports.SerializableBloomFilter = SerializableBloomFilter -exports.DummyBloomFilter = DummyBloomFilter diff --git a/extension/lib/mode-hints/hints.coffee b/extension/lib/mode-hints/hints.coffee index 28adfb9..9d424d1 100644 --- a/extension/lib/mode-hints/hints.coffee +++ b/extension/lib/mode-hints/hints.coffee @@ -18,10 +18,9 @@ # along with VimFx. If not, see . ### -utils = require('../utils') -{ getPref } = require('../prefs') -{ Marker } = require('./marker') -huffman = require('n-ary-huffman') +utils = require('../utils') +{ Marker } = require('./marker') +huffman = require('n-ary-huffman') { interfaces: Ci } = Components diff --git a/extension/lib/mode-hints/marker.coffee b/extension/lib/mode-hints/marker.coffee index 162671b..b21e308 100644 --- a/extension/lib/mode-hints/marker.coffee +++ b/extension/lib/mode-hints/marker.coffee @@ -18,16 +18,7 @@ # along with VimFx. If not, see . ### -{ createElement } = require('../utils') -{ SerializableBloomFilter -, DummyBloomFilter } = require('./bloomfilter') -{ getPref } = require('../prefs') - -HTMLDocument = Ci.nsIDOMHTMLDocument -HTMLAnchorElement = Ci.nsIDOMHTMLAnchorElement - -realBloomFilter = new SerializableBloomFilter('hints_bloom_data', 256 * 32, 16) -dummyBloomFilter = new DummyBloomFilter() +{ createElement } = require('../utils') # Wraps the markable element and provides methods to manipulate the markers. class Marker @@ -36,14 +27,6 @@ class Marker document = @element.ownerDocument @markerElement = createElement(document, 'div', {class: 'VimFxHintMarker'}) - Object.defineProperty(this, 'bloomFilter', - get: -> - if getPref('hints_bloom_on') - realBloomFilter - else - dummyBloomFilter - ) - show: -> @setVisibility(true) hide: -> @setVisibility(false) setVisibility: (visible) -> @@ -129,43 +112,4 @@ class Marker @setHint(@hintChars) @show() - # Returns string features of the element that can be used in the bloom filter - # in order to add relevance to the hint marker. - extractBloomFeatures: -> - features = {} - - # Class name of an element (walks up the node tree to find first element - # with at least one class). - suffix = '' - el = @element - while el.classList?.length == 0 and el not instanceof HTMLDocument - suffix += " #{ el.tagName }" - el = el.parentNode - if el?.classList? - for className in el.classList - features["#{ el.tagName }.#{ className }#{ suffix }"] = 10 - - if @element.id - features["#{ el.tagName }.#{ @element.id }"] = 5 - - if @element instanceof HTMLAnchorElement - features['a'] = 20 # Reward links no matter what. - features["#{ el.tagName }.#{ @element.href }"] = 60 - features["#{ el.tagName }.#{ @element.title }"] = 40 - - return features - - # Returns rating of all present bloom features (plus 1). - calcBloomRating: -> - rating = 1 - for feature, weight of @extractBloomFeatures() - rating += if @bloomFilter.test(feature) then weight else 0 - - return rating - - reward: -> - for feature, weight of @extractBloomFeatures() - @bloomFilter.add(feature) - @bloomFilter.save() - exports.Marker = Marker diff --git a/extension/lib/mode-hints/mode-hints.coffee b/extension/lib/mode-hints/mode-hints.coffee index 2c3da1a..90d55eb 100644 --- a/extension/lib/mode-hints/mode-hints.coffee +++ b/extension/lib/mode-hints/mode-hints.coffee @@ -58,7 +58,6 @@ exports.mode_hints = marker.matchHintChar(keyStr) if marker.isMatched() - marker.reward() # Add element features to the bloom filter. dontEnterNormalMode = callback(marker, markers) vim.enterMode('normal') unless dontEnterNormalMode break diff --git a/extension/locale/de/options.dtd b/extension/locale/de/options.dtd index 1684f21..8b2ef1f 100644 --- a/extension/locale/de/options.dtd +++ b/extension/locale/de/options.dtd @@ -12,9 +12,6 @@ - - - diff --git a/extension/locale/el-GR/options.dtd b/extension/locale/el-GR/options.dtd index 92b8a2f..b49aff5 100644 --- a/extension/locale/el-GR/options.dtd +++ b/extension/locale/el-GR/options.dtd @@ -13,9 +13,6 @@ - - - diff --git a/extension/locale/en-US/options.dtd b/extension/locale/en-US/options.dtd index f22c4f2..661a0b9 100644 --- a/extension/locale/en-US/options.dtd +++ b/extension/locale/en-US/options.dtd @@ -13,9 +13,6 @@ Wildcards allowed: *, !. Example: *example.com*,*foobar.org*."> - - - diff --git a/extension/locale/hu/options.dtd b/extension/locale/hu/options.dtd index 7774815..c722d1d 100644 --- a/extension/locale/hu/options.dtd +++ b/extension/locale/hu/options.dtd @@ -12,9 +12,6 @@ - - - diff --git a/extension/locale/id/options.dtd b/extension/locale/id/options.dtd index b667146..bb74eff 100644 --- a/extension/locale/id/options.dtd +++ b/extension/locale/id/options.dtd @@ -13,9 +13,6 @@ Wildcard dibolehkan: *, !. Example: *example.com*,*foobar.org*"> - - - diff --git a/extension/locale/it/options.dtd b/extension/locale/it/options.dtd index dca5bf2..ebbfdfe 100644 --- a/extension/locale/it/options.dtd +++ b/extension/locale/it/options.dtd @@ -13,9 +13,6 @@ Wildcards permesse: *, !. Esempio: *example.com*,*foobar.org*"> - - - diff --git a/extension/locale/ja/options.dtd b/extension/locale/ja/options.dtd index 5f31c5c..3a288ab 100644 --- a/extension/locale/ja/options.dtd +++ b/extension/locale/ja/options.dtd @@ -13,9 +13,6 @@ - - - diff --git a/extension/locale/nl/options.dtd b/extension/locale/nl/options.dtd index 1849bcf..1ff2de8 100644 --- a/extension/locale/nl/options.dtd +++ b/extension/locale/nl/options.dtd @@ -13,9 +13,6 @@ Speciale tekens toegestaan: *, !. Example: *example.com*,*foobar.org*"> - - - diff --git a/extension/locale/pl/options.dtd b/extension/locale/pl/options.dtd index 5a6d9a4..e2bdd29 100644 --- a/extension/locale/pl/options.dtd +++ b/extension/locale/pl/options.dtd @@ -13,9 +13,6 @@ Dopuszczalne wieloznaczniki: *, !. Domyślnie: *mail.google.com*"> - - - diff --git a/extension/locale/ru/options.dtd b/extension/locale/ru/options.dtd index d18b8e2..36a6246 100644 --- a/extension/locale/ru/options.dtd +++ b/extension/locale/ru/options.dtd @@ -13,9 +13,6 @@ - - - diff --git a/extension/locale/sv-SE/options.dtd b/extension/locale/sv-SE/options.dtd index cbbd894..8a882b7 100644 --- a/extension/locale/sv-SE/options.dtd +++ b/extension/locale/sv-SE/options.dtd @@ -13,9 +13,6 @@ Jokertecken tillåts: *, !. Exempel: *example.com*,*foobar.org*."> - - - diff --git a/extension/locale/zh-CN/options.dtd b/extension/locale/zh-CN/options.dtd index c9d3d76..b42c328 100644 --- a/extension/locale/zh-CN/options.dtd +++ b/extension/locale/zh-CN/options.dtd @@ -13,9 +13,6 @@ - - - diff --git a/extension/locale/zh-TW/options.dtd b/extension/locale/zh-TW/options.dtd index 3d994b8..643fa1b 100644 --- a/extension/locale/zh-TW/options.dtd +++ b/extension/locale/zh-TW/options.dtd @@ -13,9 +13,6 @@ - - - diff --git a/extension/options.xul b/extension/options.xul index 37bfe3b..a19464b 100644 --- a/extension/options.xul +++ b/extension/options.xul @@ -34,8 +34,6 @@ along with VimFx. If not, see . title="&pref.next_patterns.title;" desc="&pref.next_patterns.desc;" /> -