Home | History | Annotate | Download | only in sources 
      1 /*
      2  * Copyright (C) 2013 Google Inc. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions are
      6  * met:
      7  *
      8  *     * Redistributions of source code must retain the above copyright
      9  * notice, this list of conditions and the following disclaimer.
     10  *     * Redistributions in binary form must reproduce the above
     11  * copyright notice, this list of conditions and the following disclaimer
     12  * in the documentation and/or other materials provided with the
     13  * distribution.
     14  *     * Neither the name of Google Inc. nor the names of its
     15  * contributors may be used to endorse or promote products derived from
     16  * this software without specific prior written permission.
     17  *
     18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29  */
     30 
     31 /**
     32  * @constructor
     33  * @param {string} query
     34  */
     35 WebInspector.FilePathScoreFunction = function(query)
     36 {
     37     this._query = query;
     38     this._queryUpperCase = query.toUpperCase();
     39     this._score = null;
     40     this._sequence = null;
     41     this._dataUpperCase = "";
     42     this._fileNameIndex = 0;
     43 }
     44 
     45 /**
     46  * @param {string} query
     47  * @return {!RegExp}
     48  */
     49 WebInspector.FilePathScoreFunction.filterRegex = function(query)
     50 {
     51     const toEscape = String.regexSpecialCharacters();
     52     var regexString = "";
     53     for (var i = 0; i < query.length; ++i) {
     54         var c = query.charAt(i);
     55         if (toEscape.indexOf(c) !== -1)
     56             c = "\\" + c;
     57         if (i)
     58             regexString += "[^" + c + "]*";
     59         regexString += c;
     60     }
     61     return new RegExp(regexString, "i");
     62 }
     63 
     64 WebInspector.FilePathScoreFunction.prototype = {
     65     /**
     66      * @param {string} data
     67      * @param {?Array.<!Number>} matchIndexes
     68      * @return {number}
     69      */
     70     score: function(data, matchIndexes)
     71     {
     72         if (!data || !this._query)
     73             return 0;
     74         var n = this._query.length;
     75         var m = data.length;
     76         if (!this._score || this._score.length < n * m) {
     77             this._score = new Int32Array(n * m * 2);
     78             this._sequence = new Int32Array(n * m * 2);
     79         }
     80         var score = this._score;
     81         var sequence = /** @type {!Int32Array} */ (this._sequence);
     82         this._dataUpperCase = data.toUpperCase();
     83         this._fileNameIndex = data.lastIndexOf("/");
     84         for (var i = 0; i < n; ++i) {
     85             for (var j = 0; j < m; ++j) {
     86                 var skipCharScore = j === 0 ? 0 : score[i * m + j - 1];
     87                 var prevCharScore = i === 0 || j === 0 ? 0 : score[(i - 1) * m + j - 1];
     88                 var consecutiveMatch = i === 0 || j === 0 ? 0 : sequence[(i - 1) * m + j - 1];
     89                 var pickCharScore = this._match(this._query, data, i, j, consecutiveMatch);
     90                 if (pickCharScore && prevCharScore + pickCharScore > skipCharScore) {
     91                     sequence[i * m + j] = consecutiveMatch + 1;
     92                     score[i * m + j] = (prevCharScore + pickCharScore);
     93                 } else {
     94                     sequence[i * m + j] = 0;
     95                     score[i * m + j] = skipCharScore;
     96                 }
     97             }
     98         }
     99         if (matchIndexes)
    100             this._restoreMatchIndexes(sequence, n, m, matchIndexes);
    101         return score[n * m - 1];
    102     },
    103 
    104     /**
    105      * @param {string} data
    106      * @param {number} j
    107      * @return {boolean}
    108      */
    109     _testWordStart: function(data, j)
    110     {
    111         var prevChar = data.charAt(j - 1);
    112         return j === 0 || prevChar === "_" || prevChar === "-" || prevChar === "/" ||
    113             (data[j - 1] !== this._dataUpperCase[j - 1] && data[j] === this._dataUpperCase[j]);
    114     },
    115 
    116     /**
    117      * @param {!Int32Array} sequence
    118      * @param {number} n
    119      * @param {number} m
    120      * @param {!Array.<!Number>} out
    121      */
    122     _restoreMatchIndexes: function(sequence, n, m, out)
    123     {
    124         var i = n - 1, j = m - 1;
    125         while (i >= 0 && j >= 0) {
    126             switch (sequence[i * m + j]) {
    127             case 0:
    128                 --j;
    129                 break;
    130             default:
    131                 out.push(j);
    132                 --i;
    133                 --j;
    134                 break;
    135             }
    136         }
    137         out.reverse();
    138     },
    139 
    140     /**
    141      * @param {string} query
    142      * @param {string} data
    143      * @param {number} i
    144      * @param {number} j
    145      * @return {number}
    146      */
    147     _singleCharScore: function(query, data, i, j)
    148     {
    149         var isWordStart = this._testWordStart(data, j);
    150         var isFileName = j > this._fileNameIndex;
    151         var isPathTokenStart = j === 0 || data[j - 1] === "/";
    152         var isCapsMatch = query[i] === data[j] && query[i] == this._queryUpperCase[i];
    153         var score = 10;
    154         if (isPathTokenStart)
    155             score += 4;
    156         if (isWordStart)
    157             score += 2;
    158         if (isCapsMatch)
    159             score += 6;
    160         if (isFileName)
    161             score += 4;
    162         // promote the case of making the whole match in the filename
    163         if (j === this._fileNameIndex + 1 && i === 0)
    164             score += 5;
    165         if (isFileName && isWordStart)
    166             score += 3;
    167         return score;
    168     },
    169 
    170     /**
    171      * @param {string} query
    172      * @param {string} data
    173      * @param {number} i
    174      * @param {number} j
    175      * @param {number} sequenceLength
    176      * @return {number}
    177      */
    178     _sequenceCharScore: function(query, data, i, j, sequenceLength)
    179     {
    180         var isFileName = j > this._fileNameIndex;
    181         var isPathTokenStart = j === 0 || data[j - 1] === "/";
    182         var score = 10;
    183         if (isFileName)
    184             score += 4;
    185         if (isPathTokenStart)
    186             score += 5;
    187         score += sequenceLength * 4;
    188         return score;
    189     },
    190 
    191     /**
    192      * @param {string} query
    193      * @param {string} data
    194      * @param {number} i
    195      * @param {number} j
    196      * @param {number} consecutiveMatch
    197      * @return {number}
    198      */
    199     _match: function(query, data, i, j, consecutiveMatch)
    200     {
    201         if (this._queryUpperCase[i] !== this._dataUpperCase[j])
    202             return 0;
    203 
    204         if (!consecutiveMatch)
    205             return this._singleCharScore(query, data, i, j);
    206         else
    207             return this._sequenceCharScore(query, data, i, j - consecutiveMatch, consecutiveMatch);
    208     },
    209 }
    210 
    211