← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to src/core/MonoDevelop.Core/MonoDevelop.Core.Text/LaneStringMatcher.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/MonoDevelop.Core/MonoDevelop.Core.Text/LaneStringMatcher.cs
 
1
// 
 
2
// LaneStringMatcher.cs
 
3
//  
 
4
// Author:
 
5
//       Lluis Sanchez Gual <lluis@novell.com>
 
6
// 
 
7
// Copyright (c) 2010 Novell, Inc (http://www.novell.com)
 
8
// 
 
9
// Permission is hereby granted, free of charge, to any person obtaining a copy
 
10
// of this software and associated documentation files (the "Software"), to deal
 
11
// in the Software without restriction, including without limitation the rights
 
12
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 
13
// copies of the Software, and to permit persons to whom the Software is
 
14
// furnished to do so, subject to the following conditions:
 
15
// 
 
16
// The above copyright notice and this permission notice shall be included in
 
17
// all copies or substantial portions of the Software.
 
18
// 
 
19
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
20
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
21
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 
22
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 
23
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 
24
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 
25
// THE SOFTWARE.
 
26
 
 
27
using System;
 
28
using System.Collections.Generic;
 
29
 
 
30
namespace MonoDevelop.Core.Text
 
31
{
 
32
        class LaneStringMatcher: StringMatcher
 
33
        {
 
34
                readonly string filter;
 
35
                readonly string filterLowerCase;
 
36
                readonly List<MatchLane> matchLanes;
 
37
                
 
38
                public LaneStringMatcher (string filter)
 
39
                {
 
40
                        matchLanes = new List<MatchLane> ();
 
41
                        this.filter = filter;
 
42
                        this.filterLowerCase = filter != null ? filter.ToLowerInvariant () : "";
 
43
                }
 
44
 
 
45
                public override bool CalcMatchRank (string name, out int matchRank)
 
46
                {
 
47
                        if (filterLowerCase.Length == 0) {
 
48
                                matchRank = int.MinValue;
 
49
                                return true;
 
50
                        }
 
51
                        int totalWords;
 
52
                        MatchLane lane = MatchString (name, out totalWords);
 
53
                        if (lane != null) {
 
54
                                matchRank = filterLowerCase.Length - name.Length;
 
55
                                matchRank -= lane.Positions [0];
 
56
                                
 
57
                                matchRank += (lane.WordStartsMatched - totalWords) * 100;
 
58
                                
 
59
                                // Favor matches where all parts are word starts
 
60
                                if (lane.WordStartsMatched == lane.Index + 1)
 
61
                                        matchRank += 100;
 
62
                                
 
63
                                // Favor matches with less splits. That is, 'abc def' is better than 'ab c def'.
 
64
                                int baseRank = (filter.Length - lane.Index - 1) * 5000;
 
65
 
 
66
                                // First matching letter close to the begining is better
 
67
                                // The more matched letters the better
 
68
                                matchRank = baseRank - (lane.Positions [0] + (name.Length - filterLowerCase.Length));
 
69
                                
 
70
                                matchRank += lane.ExactCaseMatches * 10;
 
71
                                
 
72
                                // rank up matches which start with a filter substring
 
73
                                if (lane.Positions [0] == 0)
 
74
                                        matchRank += lane.Lengths[0] * 50;
 
75
 
 
76
                                return true;
 
77
                        }
 
78
                        matchRank = int.MinValue;
 
79
                        return false;
 
80
                }
 
81
 
 
82
                public override bool IsMatch (string name)
 
83
                {
 
84
                        int totalWords;
 
85
                        return filterLowerCase.Length == 0 || MatchString (name, out totalWords) != null;
 
86
                }
 
87
                
 
88
                /// <summary>
 
89
                /// Gets the match indices.
 
90
                /// </summary>
 
91
                /// <returns>
 
92
                /// The indices in the text which are matched by our filter.
 
93
                /// </returns>
 
94
                /// <param name='text'>
 
95
                /// The text to match.
 
96
                /// </param>
 
97
                public override int[] GetMatch (string text)
 
98
                {
 
99
                        if (filterLowerCase.Length == 0) 
 
100
                                return new int[0];
 
101
                        if (string.IsNullOrEmpty (text))
 
102
                                return null;
 
103
                        int totalWords;
 
104
                        var lane = MatchString (text, out totalWords);
 
105
                        if (lane == null)
 
106
                                return null;
 
107
                        int cnt = 0;
 
108
                        for (int i = 0; i <= lane.Index; i++) {
 
109
                                cnt += lane.Lengths[i];
 
110
                        }
 
111
                        int[] result = new int [cnt];
 
112
                        int x = 0;
 
113
                        for (int i = 0; i <= lane.Index; i++) {
 
114
                                int p = lane.Positions[i];
 
115
                                for (int j = 0 ; j < lane.Lengths[i]; j++) {
 
116
                                        result[x++] = p++;
 
117
                                }
 
118
                        }
 
119
                        return result;
 
120
                }
 
121
                
 
122
                MatchLane MatchString (string text, out int totalWords)
 
123
                {
 
124
                        totalWords = 0;
 
125
                        
 
126
                        if (text == null || text.Length < filterLowerCase.Length)
 
127
                                return null;
 
128
                        
 
129
                        // Pre-match check
 
130
                        
 
131
                        string textLowerCase = text.ToLowerInvariant ();
 
132
        
 
133
                        bool lastWasSeparator = false;
 
134
                        int firstMatchPos = -1;
 
135
                        int j = 0;
 
136
                        int tlen = text.Length;
 
137
                        int flen = filterLowerCase.Length;
 
138
                        for (int n=0; n<tlen && j < flen; n++) {
 
139
                                char ctLower = textLowerCase[n];
 
140
                                char cfLower = filterLowerCase [j];
 
141
                                bool wordStart = (ctLower != text[n]) || n == 0 || lastWasSeparator;
 
142
                                if (wordStart)
 
143
                                        totalWords++;
 
144
                                if (ctLower == cfLower && !(cfLower != filter[j] && ctLower == text[n])) {
 
145
                                        bool exactMatch = filter[j] == text[n];
 
146
                                        j++;
 
147
                                        if (firstMatchPos == -1)
 
148
                                                firstMatchPos = n;
 
149
                                        if (flen == 1) {
 
150
                                                MatchLane lane = CreateLane (MatchMode.Substring, n);
 
151
                                                if (exactMatch)
 
152
                                                        lane.ExactCaseMatches++;
 
153
                                                return lane;
 
154
                                        }
 
155
                                }
 
156
                                lastWasSeparator = IsSeparator (ctLower);
 
157
                        }
 
158
 
 
159
                        if (j < flen)
 
160
                                return null;
 
161
                        
 
162
                        ResetLanePool ();
 
163
                        
 
164
                        // Full match check
 
165
                        
 
166
                        matchLanes.Clear ();
 
167
                        int tn = firstMatchPos;
 
168
                        char filterStartLower = filterLowerCase[0];
 
169
                        bool filterStartIsUpper = filterStartLower != filter[0];
 
170
                        
 
171
                        while (tn < text.Length) {
 
172
                                char ct = text [tn];
 
173
                                char ctLower = textLowerCase [tn];
 
174
                                bool ctIsUpper = ct != ctLower;
 
175
                                bool wordStart = ctIsUpper || tn == 0 || lastWasSeparator;
 
176
                                
 
177
                                if (wordStart)
 
178
                                        totalWords++;
 
179
                                
 
180
                                // Keep the lane count in a var because new lanes don't have to be updated
 
181
                                // until the next iteration
 
182
                                int laneCount = matchLanes != null ? matchLanes.Count : 0;
 
183
        
 
184
                                if (ctLower == filterStartLower && !(filterStartIsUpper && !ctIsUpper)) {
 
185
                                        MatchLane lane = CreateLane (MatchMode.Substring, tn);
 
186
                                        if (filterStartIsUpper == ctIsUpper)
 
187
                                                lane.ExactCaseMatches++;
 
188
                                        matchLanes.Add (lane);
 
189
                                        if (filterLowerCase.Length == 1)
 
190
                                                return matchLanes[0];
 
191
                                        if (ctIsUpper || lastWasSeparator)
 
192
                                                matchLanes.Add (CreateLane (MatchMode.Acronym, tn));
 
193
                                }
 
194
        
 
195
                                for (int n=0; n<laneCount; n++) {
 
196
                                        MatchLane lane = matchLanes [n];
 
197
                                        if (lane == null)
 
198
                                                continue;
 
199
                                        char cfLower = filterLowerCase [lane.MatchIndex];
 
200
                                        bool cfIsUpper = cfLower != filter [lane.MatchIndex];
 
201
                                        bool match = ctLower == cfLower && !(cfIsUpper && !ctIsUpper);
 
202
                                        bool exactMatch = match && (cfIsUpper == ctIsUpper);
 
203
                                        bool wordStartMatch = match && wordStart;
 
204
        
 
205
                                        if (lane.MatchMode == MatchMode.Substring) {
 
206
                                                if (wordStartMatch && !LaneExists (MatchMode.Acronym, lane.MatchIndex + 1)) {
 
207
                                                        // Possible acronym match after a substring. Start a new lane.
 
208
                                                        MatchLane newLane = CloneLane (lane);
 
209
                                                        newLane.MatchMode = MatchMode.Acronym;
 
210
                                                        newLane.WordStartsMatched++;
 
211
                                                        newLane.Index++;
 
212
                                                        newLane.Positions [newLane.Index] = tn;
 
213
                                                        newLane.Lengths [newLane.Index] = 1;
 
214
                                                        newLane.MatchIndex++;
 
215
                                                        if (exactMatch)
 
216
                                                                newLane.ExactCaseMatches++;
 
217
                                                        matchLanes.Add (newLane);
 
218
                                                }
 
219
                                                if (match) {
 
220
                                                        if (!LaneExists (MatchMode.Acronym, lane.MatchIndex)) {
 
221
                                                                // Maybe it is a false substring start, so add a new lane to keep
 
222
                                                                // track of the old lane
 
223
                                                                MatchLane newLane = CloneLane (lane);
 
224
                                                                newLane.MatchMode = MatchMode.Acronym;
 
225
                                                                matchLanes.Add (newLane);
 
226
                                                                if (exactMatch)
 
227
                                                                        newLane.ExactCaseMatches++;
 
228
                                                        }
 
229
        
 
230
                                                        // Update the current lane
 
231
                                                        lane.Lengths [lane.Index]++;
 
232
                                                        lane.MatchIndex++;
 
233
                                                } else {
 
234
                                                        if (lane.Lengths [lane.Index] > 1)
 
235
                                                                lane.MatchMode = MatchMode.Acronym;
 
236
                                                        else
 
237
                                                                matchLanes [n] = null; // Kill the lane
 
238
                                                }
 
239
                                        }
 
240
                                        else if (lane.MatchMode == MatchMode.Acronym) {
 
241
                                                if (match && lane.Positions [lane.Index] == tn - 1 && !LaneExists (MatchMode.Substring, lane.MatchIndex + 1)) {
 
242
                                                        // Possible substring match after an acronim. Start a new lane.
 
243
                                                        MatchLane newLane = CloneLane (lane);
 
244
                                                        newLane.MatchMode = MatchMode.Substring;
 
245
                                                        newLane.Lengths [newLane.Index]++;
 
246
                                                        newLane.MatchIndex++;
 
247
                                                        if (exactMatch)
 
248
                                                                newLane.ExactCaseMatches++;
 
249
                                                        matchLanes.Add (newLane);
 
250
                                                        if (newLane.MatchIndex == filterLowerCase.Length)
 
251
                                                                return newLane;
 
252
                                                }
 
253
                                                if ((wordStartMatch || (match && char.IsPunctuation (cfLower))) && !LaneExists (MatchMode.Acronym, lane.MatchIndex + 1)) {
 
254
                                                        // Maybe it is a false acronym start, so add a new lane to keep
 
255
                                                        // track of the old lane
 
256
                                                        MatchLane newLane = CloneLane (lane);
 
257
                                                        matchLanes.Add (newLane);
 
258
        
 
259
                                                        // Update the current lane
 
260
                                                        lane.Index++;
 
261
                                                        lane.Positions [lane.Index] = tn;
 
262
                                                        lane.Lengths [lane.Index] = 1;
 
263
                                                        lane.MatchIndex++;
 
264
                                                        if (wordStartMatch)
 
265
                                                                lane.WordStartsMatched++;
 
266
                                                        if (exactMatch)
 
267
                                                                newLane.ExactCaseMatches++;
 
268
                                                }
 
269
                                        }
 
270
                                        if (lane.MatchIndex == filterLowerCase.Length)
 
271
                                                return lane;
 
272
                                }
 
273
                                lastWasSeparator = IsSeparator (ct);
 
274
                                tn++;
 
275
                        }
 
276
                        return null;
 
277
                }
 
278
                
 
279
                bool LaneExists (MatchMode mode, int matchIndex)
 
280
                {
 
281
                        if (matchLanes == null)
 
282
                                return false;
 
283
                        for (int n=0; n<matchLanes.Count; n++) {
 
284
                                MatchLane lane = matchLanes [n];
 
285
                                if (lane != null && lane.MatchMode == mode && lane.MatchIndex == matchIndex)
 
286
                                        return true;
 
287
                        }
 
288
                        return false;
 
289
                }
 
290
                
 
291
                bool IsSeparator (char ct)
 
292
                {
 
293
                        return (ct == '.' || ct == '_' || ct == '-' || ct == ' ' || ct == '/' || ct == '\\');
 
294
                }
 
295
                
 
296
                void ResetLanePool ()
 
297
                {
 
298
                        lanePoolIndex = 0;
 
299
                }
 
300
                
 
301
                MatchLane GetPoolLane ()
 
302
                {
 
303
                        if (lanePoolIndex < lanePool.Count)
 
304
                                return lanePool [lanePoolIndex++];
 
305
                        
 
306
                        MatchLane lane = new MatchLane (filterLowerCase.Length * 2);
 
307
                        lanePool.Add (lane);
 
308
                        lanePoolIndex++;
 
309
                        return lane;
 
310
                }
 
311
                
 
312
                MatchLane CreateLane (MatchMode mode, int pos)
 
313
                {
 
314
                        MatchLane lane = GetPoolLane ();
 
315
                        lane.Initialize (mode, pos);
 
316
                        if (mode == MatchMode.Acronym)
 
317
                                lane.WordStartsMatched = 1;
 
318
                        return lane;
 
319
                }
 
320
                
 
321
                MatchLane CloneLane (MatchLane other)
 
322
                {
 
323
                        MatchLane lane = GetPoolLane ();
 
324
                        lane.Initialize (other);
 
325
                        return lane;
 
326
                }
 
327
                
 
328
                int lanePoolIndex = 0;
 
329
                List<MatchLane> lanePool = new List<MatchLane> ();
 
330
        
 
331
                enum MatchMode {
 
332
                        Substring,
 
333
                        Acronym
 
334
                }
 
335
        
 
336
                class MatchLane
 
337
                {
 
338
                        public int[] Positions;
 
339
                        public int[] Lengths;
 
340
                        public MatchMode MatchMode;
 
341
                        public int Index;
 
342
                        public int MatchIndex;
 
343
                        public int ExactCaseMatches;
 
344
                        public int WordStartsMatched;
 
345
        
 
346
                        public MatchLane (int maxlen)
 
347
                        {
 
348
                                Positions = new int [maxlen];
 
349
                                Lengths = new int [maxlen];
 
350
                        }
 
351
                        
 
352
                        public void Initialize (MatchMode mode, int pos)
 
353
                        {
 
354
                                MatchMode = mode;
 
355
                                Positions [0] = pos;
 
356
                                Lengths [0] = 1;
 
357
                                Index = 0;
 
358
                                MatchIndex = 1;
 
359
                                ExactCaseMatches = 0;
 
360
                                WordStartsMatched = 0;
 
361
                        }
 
362
        
 
363
                        public void Initialize (MatchLane other)
 
364
                        {
 
365
                                for (int n=0; n<=other.Index; n++) {
 
366
                                        Positions [n] = other.Positions [n];
 
367
                                        Lengths [n] = other.Lengths [n];
 
368
                                }
 
369
                                MatchMode = other.MatchMode;
 
370
                                MatchIndex = other.MatchIndex;
 
371
                                Index = other.Index;
 
372
                                ExactCaseMatches = other.ExactCaseMatches;
 
373
                                WordStartsMatched = other.WordStartsMatched;
 
374
                        }
 
375
                }
 
376
        }
 
377
}
 
378