author | Quentin Pradet <quentin.pradet@gmail.com> |
Fri, 07 Sep 2012 14:24:58 +0100 | |
changeset 104680 | dea1d12241078657308813fb1db8fd6699ce5c51 |
parent 104679 | c606437fca80ed51de32f00f57db5022c58bbb63 |
child 104681 | aaa9837d68b3761deff184ae7ac9197fd34c7c38 |
push id | 23438 |
push user | ttaubert@mozilla.com |
push date | Mon, 10 Sep 2012 07:47:22 +0000 |
treeherder | mozilla-central@1cb30394aa56 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | jwalker |
bugs | 764856 |
milestone | 18.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
--- a/browser/devtools/commandline/gcli.jsm +++ b/browser/devtools/commandline/gcli.jsm @@ -1702,17 +1702,17 @@ exports.ArrayArgument = ArrayArgument; define('gcli/types/selection', ['require', 'exports', 'module' , 'gcli/l10n', 'gcli/types', 'gcli/types/spell'], function(require, exports, module) { var l10n = require('gcli/l10n'); var types = require('gcli/types'); var Type = require('gcli/types').Type; var Status = require('gcli/types').Status; var Conversion = require('gcli/types').Conversion; -var Speller = require('gcli/types/spell').Speller; +var spell = require('gcli/types/spell'); /** * Registration and de-registration. */ exports.startup = function() { types.registerType(SelectionType); }; @@ -1883,23 +1883,24 @@ SelectionType.prototype._findPredictions if (predictions.indexOf(option) === -1) { this._addToPredictions(predictions, option, arg); } } } } // Try fuzzy matching if we don't get a prefix match - if (false && predictions.length === 0) { - var speller = new Speller(); - var names = lookup.map(function(opt) { - return opt.name; + if (predictions.length === 0) { + var names = []; + lookup.forEach(function(opt) { + if (!opt.value.hidden) { + names.push(opt.name); + } }); - speller.train(names); - var corrected = speller.correct(match); + var corrected = spell.correct(match, names); if (corrected) { lookup.forEach(function(opt) { if (opt.name === corrected) { predictions.push(opt); } }, this); } } @@ -2000,163 +2001,126 @@ SelectionType.prototype._findValue = fun SelectionType.prototype.name = 'selection'; exports.SelectionType = SelectionType; }); /* - * Copyright (c) 2009 Panagiotis Astithas - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY - * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION - * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN - * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * Copyright 2012, Mozilla Foundation and contributors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. */ define('gcli/types/spell', ['require', 'exports', 'module' ], function(require, exports, module) { - -/** - * A spell-checker based on the statistical algorithm described by Peter Norvig - * in http://norvig.com/spell-correct.html, and converted to JavaScript by Past - * http://past.github.com/speller/ - * - * Usage requires a two-step process: - * 1) call speller.train() one or more times with a large text to train the - * language model - * 2) call speller.correct(word) to retrieve the correction for the specified - * word - */ -function Speller() { - // A map of words to the count of times they were encountered during training. - this._nWords = {}; -} - -Speller.letters = "abcdefghijklmnopqrstuvwxyz".split(""); - -/** - * A function that trains the language model with the words in the supplied - * text. Multiple invocation of this function can extend the training of the - * model. - */ -Speller.prototype.train = function(words) { - words.forEach(function(word) { - word = word.toLowerCase(); - this._nWords[word] = this._nWords.hasOwnProperty(word) ? - this._nWords[word] + 1 : - 1; - }, this); +/* + * A spell-checker based on Damerau-Levenshtein distance. + */ + +var INSERTION_COST = 1; +var DELETION_COST = 1; +var SWAP_COST = 1; +var SUBSTITUTION_COST = 2; +var MAX_EDIT_DISTANCE = 4; + +/** + * Compute Damerau-Levenshtein Distance + * @see http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance + */ +function damerauLevenshteinDistance(wordi, wordj) { + var N = wordi.length; + var M = wordj.length; + + // We only need to store three rows of our dynamic programming matrix. + // (Without swap, it would have been two.) + var row0 = new Array(N+1); + var row1 = new Array(N+1); + var row2 = new Array(N+1); + var tmp; + + var i, j; + + // The distance between the empty string and a string of size i is the cost + // of i insertions. + for (i = 0; i <= N; i++) { + row1[i] = i * INSERTION_COST; + } + + // Row-by-row, we're computing the edit distance between substrings wordi[0..i] + // and wordj[0..j]. + for (j = 1; j <= M; j++) + { + // Edit distance between wordi[0..0] and wordj[0..j] is the cost of j + // insertions. + row0[0] = j * INSERTION_COST; + + for (i = 1; i <= N; i++) + { + // Handle deletion, insertion and substitution: we can reach each cell + // from three other cells corresponding to those three operations. We + // want the minimum cost. + row0[i] = Math.min( + row0[i-1] + DELETION_COST, + row1[i] + INSERTION_COST, + row1[i-1] + (wordi[i-1] === wordj[j-1] ? 0 : SUBSTITUTION_COST)); + // We handle swap too, eg. distance between help and hlep should be 1. If + // we find such a swap, there's a chance to update row0[1] to be lower. + if (i > 1 && j > 1 && wordi[i-1] === wordj[j-2] && wordj[j-1] === wordi[i-2]) { + row0[i] = Math.min(row0[i], row2[i-2] + SWAP_COST); + } + } + + tmp = row2; + row2 = row1; + row1 = row0; + row0 = tmp; + } + + return row1[N]; }; /** * A function that returns the correction for the specified word. */ -Speller.prototype.correct = function(word) { - if (this._nWords.hasOwnProperty(word)) { - return word; - } - - var candidates = {}; - var list = this._edits(word); - list.forEach(function(edit) { - if (this._nWords.hasOwnProperty(edit)) { - candidates[this._nWords[edit]] = edit; - } - }, this); - - if (this._countKeys(candidates) > 0) { - return candidates[this._max(candidates)]; - } - - list.forEach(function(edit) { - this._edits(edit).forEach(function(w) { - if (this._nWords.hasOwnProperty(w)) { - candidates[this._nWords[w]] = w; - } - }, this); - }, this); - - return this._countKeys(candidates) > 0 ? - candidates[this._max(candidates)] : - null; -}; - -/** - * A helper function that counts the keys in the supplied object. - */ -Speller.prototype._countKeys = function(object) { - // return Object.keys(object).length; ? - var count = 0; - for (var attr in object) { - if (object.hasOwnProperty(attr)) { - count++; - } - } - return count; -}; - -/** - * A helper function that returns the word with the most occurrences in the - * language model, among the supplied candidates. - * @param candidates - */ -Speller.prototype._max = function(candidates) { - var arr = []; - for (var candidate in candidates) { - if (candidates.hasOwnProperty(candidate)) { - arr.push(candidate); - } - } - return Math.max.apply(null, arr); -}; - -/** - * A function that returns the set of possible corrections of the specified - * word. The edits can be deletions, insertions, alterations or transpositions. - */ -Speller.prototype._edits = function(word) { - var results = []; - - // Deletion - for (var i = 0; i < word.length; i++) { - results.push(word.slice(0, i) + word.slice(i + 1)); - } - - // Transposition - for (i = 0; i < word.length - 1; i++) { - results.push(word.slice(0, i) + word.slice(i + 1, i + 2) - + word.slice(i, i + 1) + word.slice(i + 2)); - } - - // Alteration - for (i = 0; i < word.length; i++) { - Speller.letters.forEach(function(l) { - results.push(word.slice(0, i) + l + word.slice(i + 1)); - }, this); - } - - // Insertion - for (i = 0; i <= word.length; i++) { - Speller.letters.forEach(function(l) { - results.push(word.slice(0, i) + l + word.slice(i)); - }, this); - } - - return results; -}; - -exports.Speller = Speller; +exports.correct = function(word, names) { + var distance = {}; + var sorted_candidates; + + names.forEach(function(candidate) { + distance[candidate] = damerauLevenshteinDistance(word, candidate); + }); + + sorted_candidates = names.sort(function(worda, wordb) { + if (distance[worda] !== distance[wordb]) { + return distance[worda] - distance[wordb]; + } else { + // if the score is the same, always return the first string + // in the lexicographical order + return worda < wordb; + } + }); + + if (distance[sorted_candidates[0]] <= MAX_EDIT_DISTANCE) { + return sorted_candidates[0]; + } else { + return undefined; + } +}; }); /* * Copyright 2012, Mozilla Foundation and contributors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License.
--- a/browser/devtools/commandline/test/browser_cmd_pref.js +++ b/browser/devtools/commandline/test/browser_cmd_pref.js @@ -158,18 +158,18 @@ function testPrefStatus() { setting: { arg: ' devtools.editor.tabsize' }, value: { value: 4 }, } }); helpers.setInput('pref list'); helpers.check({ input: 'pref list', - hints: '', - markup: 'EEEEVEEEE', + hints: ' -> pref set', + markup: 'IIIIVIIII', status: 'ERROR' }); } function testPrefSetEnable() { DeveloperToolbarTest.exec({ typed: "pref set devtools.editor.tabsize 9", args: {
--- a/browser/devtools/commandline/test/browser_gcli_web.js +++ b/browser/devtools/commandline/test/browser_gcli_web.js @@ -2345,17 +2345,17 @@ exports.testActivate = function(options) helpers.setInput('tsg b'); helpers.check({ hints: 'bb [options]' }); helpers.setInput('tsg d'); helpers.check({ - hints: ' [options]' + hints: ' [options] -> ccc' }); helpers.setInput('tsg aa'); helpers.check({ hints: 'a [options]' }); helpers.setInput('tsg aaa'); @@ -3334,19 +3334,18 @@ exports.testIncomplete = function(option test.is(requisition._unassigned[0].param.type.isIncompleteName, true, 'unassigned.isIncompleteName: tsg -'); }; exports.testHidden = function(options) { helpers.setInput('tshidde'); helpers.check({ input: 'tshidde', - markup: 'EEEEEEE', - status: 'ERROR', - hints: '', + hints: ' -> tse', + status: 'ERROR' }); helpers.setInput('tshidden'); helpers.check({ input: 'tshidden', hints: ' [options]', markup: 'VVVVVVVV', status: 'VALID', @@ -4368,17 +4367,17 @@ exports.testPrefSetStatus = function(opt hints: ' <setting> <value>', markup: 'VVVVVVVV', status: 'ERROR' }); helpers.setInput('pref xxx'); helpers.check({ typed: 'pref xxx', - markup: 'EEEEVEEE', + markup: 'IIIIVIII', status: 'ERROR' }); helpers.setInput('pref set '); helpers.check({ typed: 'pref set ', hints: 'allowSet <value>', markup: 'VVVVVVVVV', @@ -5038,39 +5037,38 @@ exports.testChange = function(options) { * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ define('gclitest/testSpell', ['require', 'exports', 'module' , 'test/assert', 'gcli/types/spell'], function(require, exports, module) { var test = require('test/assert'); -var Speller = require('gcli/types/spell').Speller; +var spell = require('gcli/types/spell'); exports.setup = function() { }; exports.shutdown = function() { }; exports.testSpellerSimple = function(options) { if (options.isFirefox) { test.log('Skipping testPref in Firefox.'); return; } - var speller = new Speller(); - speller.train(Object.keys(options.window)); - - test.is(speller.correct('document'), 'document'); - test.is(speller.correct('documen'), 'document'); - test.is(speller.correct('ocument'), 'document'); - test.is(speller.correct('odcument'), 'document'); - - test.is(speller.correct('========='), null); + var alternatives = Object.keys(options.window); + + test.is(spell.correct('document', alternatives), 'document'); + test.is(spell.correct('documen', alternatives), 'document'); + test.is(spell.correct('ocument', alternatives), 'document'); + test.is(spell.correct('odcument', alternatives), 'document'); + + test.is(spell.correct('=========', alternatives), undefined); }; }); /* * Copyright 2012, Mozilla Foundation and contributors * * Licensed under the Apache License, Version 2.0 (the "License"); @@ -5526,21 +5524,19 @@ exports.testActivate = function(options) type('tsb t', { important: true, options: [ 'true' ] }, options); type('tsb tt', { important: true, - options: [ ], - error: 'Can\'t use \'tt\'.' + options: [ 'true' ] }, options); - type('asdf', { important: false, options: [ ], error: 'Can\'t use \'asdf\'.' }, options); type('', { }, options); };