Web Inspector: Quick Open fails to match pattern "bB" in file "abBc"
[WebKit-https.git] / Source / WebInspectorUI / UserInterface / Controllers / ResourceQueryController.js
1 /*
2  * Copyright (C) 2016 Apple 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
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 WebInspector.ResourceQueryController = class ResourceQueryController extends WebInspector.Object
27 {
28     constructor()
29     {
30         super();
31
32         this._resourceDataMap = new Map;
33     }
34
35     // Public
36
37     addResource(resource)
38     {
39         this._resourceDataMap.set(resource, {});
40     }
41
42     removeResource(resource)
43     {
44         this._resourceDataMap.delete(resource);
45     }
46
47     reset()
48     {
49         this._resourceDataMap.clear();
50     }
51
52     executeQuery(query)
53     {
54         if (!query || !this._resourceDataMap.size)
55             return [];
56
57         query = query.removeWhitespace().toLowerCase();
58
59         let results = [];
60         for (let [resource, cachedData] of this._resourceDataMap) {
61             if (!cachedData.searchString) {
62                 let displayName = resource.displayName;
63                 cachedData.searchString = displayName.toLowerCase();
64                 cachedData.specialCharacterIndices = this._findSpecialCharacterIndices(displayName);
65             }
66
67             let matches = this._findQueryMatches(query, cachedData.searchString, cachedData.specialCharacterIndices);
68             if (matches.length)
69                 results.push(new WebInspector.ResourceQueryResult(resource, matches));
70         }
71
72         // Resources are sorted in descending order by rank. Resources of equal
73         // rank are sorted by display name.
74         return results.sort((a, b) => {
75             if (a.rank === b.rank)
76                 return a.resource.displayName.localeCompare(b.resource.displayName);
77             return b.rank - a.rank;
78         });
79     }
80
81     // Private
82
83     _findQueryMatches(query, searchString, specialCharacterIndices)
84     {
85         let matches = [];
86         let queryIndex = 0;
87         let searchIndex = 0;
88         let specialIndex = 0;
89         let deadBranches = new Array(query.length).fill(Infinity);
90         let type = WebInspector.ResourceQueryMatch.Type.Special;
91
92         function pushMatch(index)
93         {
94             matches.push(new WebInspector.ResourceQueryMatch(type, index, queryIndex));
95             searchIndex = index + 1;
96             queryIndex++;
97         }
98
99         function matchNextSpecialCharacter()
100         {
101             if (specialIndex >= specialCharacterIndices.length)
102                 return false;
103
104             let originalSpecialIndex = specialIndex;
105             while (specialIndex < specialCharacterIndices.length) {
106                 // Normal character matching can move past special characters,
107                 // so advance the special character index if it's before the
108                 // current search string position.
109                 let index = specialCharacterIndices[specialIndex++];
110                 if (index < searchIndex)
111                     continue;
112
113                 if (query[queryIndex] === searchString[index]) {
114                     pushMatch(index);
115                     return true;
116                 }
117             }
118
119             specialIndex = originalSpecialIndex;
120             return false;
121         }
122
123         function backtrack()
124         {
125             while (matches.length) {
126                 queryIndex--;
127
128                 let lastMatch = matches.pop();
129                 if (lastMatch.type !== WebInspector.ResourceQueryMatch.Type.Special)
130                     continue;
131
132                 deadBranches[lastMatch.queryIndex] = lastMatch.index;
133                 searchIndex = matches.lastValue ? matches.lastValue.index + 1 : 0;
134                 return true;
135             }
136
137             return false;
138         }
139
140         while (queryIndex < query.length && searchIndex < searchString.length) {
141             if (type === WebInspector.ResourceQueryMatch.Type.Special && !matchNextSpecialCharacter())
142                 type = WebInspector.ResourceQueryMatch.Type.Normal;
143
144             if (type === WebInspector.ResourceQueryMatch.Type.Normal) {
145                 let index = searchString.indexOf(query[queryIndex], searchIndex);
146                 if (index >= 0 && index < deadBranches[queryIndex]) {
147                     pushMatch(index);
148                     type = WebInspector.ResourceQueryMatch.Type.Special;
149                 } else if (!backtrack())
150                     return [];
151             }
152         }
153
154         if (queryIndex < query.length)
155             return [];
156
157         return matches;
158     }
159
160     _findSpecialCharacterIndices(string)
161     {
162         if (!string.length)
163             return [];
164
165         const filenameSeparators = "_.-";
166
167         // Special characters include the following:
168         // 1. The first character.
169         // 2. Uppercase characters that follow a lowercase letter.
170         // 3. Filename separators and the first character following the separator.
171         let indices = [0];
172
173         for (let i = 1; i < string.length; ++i) {
174             let character = string[i];
175             let isSpecial = false;
176
177             if (filenameSeparators.includes(character))
178                 isSpecial = true;
179             else {
180                 let previousCharacter = string[i - 1];
181                 let previousCharacterIsSeparator = filenameSeparators.includes(previousCharacter);
182                 if (previousCharacterIsSeparator)
183                     isSpecial = true;
184                 else if (character.isUpperCase() && previousCharacter.isLowerCase())
185                     isSpecial = true;
186             }
187
188             if (isSpecial)
189                 indices.push(i);
190         }
191
192         return indices;
193     }
194 };