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 */ 35WebInspector.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 */ 49WebInspector.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 64WebInspector.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