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 = 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