src/third_party/WebKit/Source/devtools/front_end/sources/FilePathScoreFunction.js

   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