Optimized code completion match algorithm & made it easier to re-use. The navigate to command now uses this algorithm for filtering.

A large amount of time of the navigate to dialog item list was taken by the filter - using the greedy algorithm from the code completion code makes this feature much faster & it's now more consistent with the code completion. However the old algorithm is still in there and reverting this is a small change in the NavigateToDialog - just uncomment it. When all users are satisfied with the code completion algorithm the code should be taken out.

3 files changed, 140 insertions, 71 deletions

diff --git a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/CompletionMatcher.cs b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/CompletionMatcher.cs
new file mode 100644
index 0000000000..b23c5857f2
--- /dev/null
+++ b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/CompletionMatcher.cs
@@ -0,0 +1,129 @@
+// 
+// CompletionMatcher.cs
+//  
+// Author:
+//       Mike Krüger <mkrueger@novell.com>
+// 
+// Copyright (c) 2010 Novell, Inc (http://www.novell.com)
+// 
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+// 
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+// 
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+using System;
+using System.Collections.Generic;
+
+namespace MonoDevelop.Ide.CodeCompletion
+{
+	/// <summary>
+	/// A class for computing sub word matches (ex. WL matches WriteLine).
+	/// </summary>
+	class CompletionMatcher
+	{
+		readonly string filterTextUpperCase;
+
+		readonly bool[] filterTextLowerCaseTable;
+		readonly bool[] filterIsNonLetter;
+
+		readonly List<int> matchIndices;
+
+		public CompletionMatcher (string filterText)
+		{
+			matchIndices = new List<int> ();
+			if (filterText != null) {
+				filterTextLowerCaseTable = new bool[filterText.Length];
+				filterIsNonLetter        = new bool[filterText.Length];
+				for (int  i = 0; i < filterText.Length; i++) {
+					filterTextLowerCaseTable[i] = char.IsLower (filterText[i]);
+					filterIsNonLetter[i] = !char.IsLetter (filterText[i]);
+				}
+				
+				filterTextUpperCase = filterText.ToUpper ();
+			}
+		}
+
+		public bool IsMatch (string text)
+		{
+			return GetMatch (text) != null;
+		}
+		
+		/// <summary>
+		/// Gets the match indices.
+		/// </summary>
+		/// <returns>
+		/// The indices in the text which are matched by our filter.
+		/// </returns>
+		/// <param name='text'>
+		/// The text to match.
+		/// </param>
+		public int[] GetMatch (string text)
+		{
+			if (string.IsNullOrEmpty (filterTextUpperCase))
+				return new int[0];
+			if (string.IsNullOrEmpty (text))
+				return null;
+
+			matchIndices.Clear ();
+			int j = 0;
+			
+			for (int i = 0; i < filterTextUpperCase.Length; i++) {
+				if (j >= text.Length)
+					return null;
+				bool wasMatch = false;
+				char filterChar = filterTextUpperCase[i];
+				// filter char is no letter -> search for next exact match
+				if (filterIsNonLetter[i]) {
+					for (; j < text.Length; j++) {
+						if (filterChar == text[j]) {
+							matchIndices.Add (j);
+							j++;
+							wasMatch = true;
+							break;
+						}
+					}
+					if (!wasMatch)
+						return null;
+					continue;
+				}
+				
+				// letter case
+				bool textCharIsUpper = char.IsUpper (text[j]);
+				if ((textCharIsUpper || filterTextLowerCaseTable[i]) && filterChar == (textCharIsUpper ? text[j] : char.ToUpper (text[j]))) {
+					matchIndices.Add (j++);
+					continue;
+				}
+
+				// no match, try to continue match at the next word start
+				j++;
+				for (; j < text.Length; j++) {
+					if (char.IsUpper (text[j]) && filterChar == text[j]) {
+						matchIndices.Add (j);
+						j++;
+						wasMatch = true;
+						break;
+					}
+				}
+				
+				if (!wasMatch)
+					return null;
+			}
+			
+			return matchIndices.ToArray ();
+		}
+	}
+
+}
+
diff --git a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWidget.cs b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWidget.cs
index b361c3970f..6bb3c2bf85 100644
--- a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWidget.cs
+++ b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWidget.cs
@@ -348,7 +348,7 @@ namespace MonoDevelop.Ide.CodeCompletion
 			var textGCInsensitive = this.Style.TextGC (StateType.Insensitive);
 			var textGCNormal = this.Style.TextGC (StateType.Normal);
 			var fgGCNormal = this.Style.ForegroundGC (StateType.Normal);
-			
+			CompletionMatcher matcher = new CompletionMatcher (CompletionString);
 			Iterate (true, ref yPos, delegate (Category category, int ypos) {
 				if (ypos >= height - margin)
 					return;
@@ -394,7 +394,7 @@ namespace MonoDevelop.Ide.CodeCompletion
 				string text = win.DataProvider.GetText (itemIndex);
 				
 				if ((!SelectionEnabled || item != selection) && !string.IsNullOrEmpty (text)) {
-					int[] matchIndices = Match (CompletionString, text);
+					int[] matchIndices = matcher.GetMatch (text);
 					if (matchIndices != null) {
 						Pango.AttrList attrList = layout.Attributes ?? new Pango.AttrList ();
 						for (int newSelection = 0; newSelection < matchIndices.Length; newSelection++) {
@@ -516,70 +516,6 @@ namespace MonoDevelop.Ide.CodeCompletion
 		
 		internal List<int> filteredItems = new List<int> ();
 		
-		internal static int[] Match (string filterText, string text)
-		{
-			if (string.IsNullOrEmpty (filterText))
-				return new int[0];
-			if (string.IsNullOrEmpty (text))
-				return null;
-			List<int> matchIndices = new List<int> ();
-			bool wasMatch = false;
-			int itemIndex = 0;
-			
-			for (int newSelection = 0; newSelection < text.Length && itemIndex < filterText.Length; newSelection++) {
-				char ch1 = char.ToUpper (text[newSelection]);
-				char ch2 = char.ToUpper (filterText[itemIndex]);
-				bool ch1IsUpper = char.IsUpper (text[newSelection]);
-				bool ch2IsUpper = char.IsUpper (filterText[itemIndex]);
-				
-				if (ch1 == ch2 && !(!ch1IsUpper && ch2IsUpper)) {
-					itemIndex++;
-					matchIndices.Add (newSelection);
-					wasMatch = true;
-					continue;
-				} else {
-					for (; newSelection < text.Length; newSelection++) {
-						if (char.IsUpper (text[newSelection]) /*&& newSelection + 1 < text.Length && (!char.IsUpper (text[newSelection + 1]) || !char.IsLetter (text[newSelection + 1]))*/ && ch2 == text[newSelection]) {
-							matchIndices.Add (newSelection);
-							itemIndex++;
-							wasMatch = true;
-							break;
-						}
-					}
-					if (wasMatch)
-						continue;
-				}
-				
-				if ((char.IsPunctuation (ch2) || char.IsWhiteSpace (ch2))) {
-					wasMatch = false;
-					break;
-				}
-				
-				if (wasMatch) {
-					wasMatch = false;
-					bool match = false;
-					for (; newSelection < text.Length; newSelection++) {
-						if (ch2 == text[newSelection]) {
-							newSelection--;
-							match = true;
-							break;
-						}
-					}
-					if (match)
-						continue;
-				}
-				break;
-			}
-			
-			return itemIndex == filterText.Length ? matchIndices.ToArray () : null;
-		}
-		
-				
-		public static bool Matches (string filterText, string text)
-		{
-			return Match (filterText, text) != null;
-		}
-		
 		Category GetCategory (CompletionCategory completionCategory)
 		{
 			foreach (Category cat in categories) {
@@ -600,8 +536,9 @@ namespace MonoDevelop.Ide.CodeCompletion
 		{
 			filteredItems.Clear ();
 			categories.Clear ();
+			CompletionMatcher matcher = new CompletionMatcher (CompletionString);
 			for (int newSelection = 0; newSelection < win.DataProvider.ItemCount; newSelection++) {
-				if (string.IsNullOrEmpty (CompletionString) || Matches (CompletionString, win.DataProvider.GetText (newSelection))) {
+				if (string.IsNullOrEmpty (CompletionString) || matcher.IsMatch (win.DataProvider.GetText (newSelection))) {
 					CompletionCategory completionCategory = win.DataProvider.GetCompletionCategory (newSelection);
 					GetCategory (completionCategory).Items.Add (filteredItems.Count);
 					filteredItems.Add (newSelection);
diff --git a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWindow.cs b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWindow.cs
index e04d82b72d..19b581a21a 100644
--- a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWindow.cs
+++ b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/ListWindow.cs
@@ -405,18 +405,20 @@ namespace MonoDevelop.Ide.CodeCompletion
 		class WordComparer : IComparer <KeyValuePair<int, string>>
 		{
 			string filterWord;
+			CompletionMatcher matcher;
 
 			public WordComparer (string filterWord)
 			{
 				this.filterWord = filterWord ?? "";
+				matcher = new CompletionMatcher (filterWord);
 			}
 			
 			public int Compare (KeyValuePair<int, string> xpair, KeyValuePair<int, string> ypair)
 			{
 				string x = xpair.Value;
 				string y = ypair.Value;
-				int[] xMatches = ListWidget.Match (filterWord, x) ?? new int[0];
-				int[] yMatches = ListWidget.Match (filterWord, y) ?? new int[0];
+				int[] xMatches = matcher.GetMatch (x) ?? new int[0];
+				int[] yMatches = matcher.GetMatch (y) ?? new int[0];
 				if (xMatches.Length < yMatches.Length) 
 					return 1;
 				if (xMatches.Length > yMatches.Length) 
@@ -455,13 +457,14 @@ namespace MonoDevelop.Ide.CodeCompletion
 			// default - word with highest match rating in the list.
 			hasMismatches = true;
 			int idx = -1;
+			CompletionMatcher matcher = new CompletionMatcher (partialWord);
 			
 			List<KeyValuePair<int, string>> words = new List<KeyValuePair<int, string>> ();
 			if (!string.IsNullOrEmpty (partialWord)) {
 				for (int i = 0; i < list.filteredItems.Count; i++) {
 					int index = list.filteredItems[i];
 					string text = DataProvider.GetCompletionText (index);
-					if (!ListWidget.Matches (partialWord, text))
+					if (!matcher.IsMatch (text))
 						continue;
 					words.Add (new KeyValuePair <int,string> (i, text));
 				}
@@ -481,7 +484,7 @@ namespace MonoDevelop.Ide.CodeCompletion
 				// Search for history matches.
 				for (int i = 0; i < wordHistory.Count; i++) {
 					string historyWord = wordHistory[i];
-					if (ListWidget.Matches (partialWord, historyWord)) {
+					if (matcher.IsMatch (historyWord)) {
 						for (int xIndex = 0; xIndex < list.filteredItems.Count; xIndex++) {
 							string currentWord = DataProvider.GetCompletionText (list.filteredItems[xIndex]);
 							if (currentWord == historyWord) {