Worked on completion matcher.

1 files changed, 167 insertions, 61 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
index b23c5857f2..6f57e181f9 100644
--- a/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/CompletionMatcher.cs
+++ b/main/src/core/MonoDevelop.Ide/MonoDevelop.Ide.CodeCompletion/CompletionMatcher.cs
@@ -33,31 +33,34 @@ namespace MonoDevelop.Ide.CodeCompletion
 	/// </summary>
 	class CompletionMatcher
 	{
-		readonly string filterTextUpperCase;
-
-		readonly bool[] filterTextLowerCaseTable;
-		readonly bool[] filterIsNonLetter;
-
-		readonly List<int> matchIndices;
+		readonly string filterLowerCase;
+		
+		readonly List<MatchLane> matchLanes;
+		
+		public CompletionMatcher (string filter)
+		{
+			matchLanes = new List<MatchLane> ();
+			this.filterLowerCase = filter != null ? filter.ToLower () : "";
+		}
 
-		public CompletionMatcher (string filterText)
+		public bool CalcMatchRank (string name, out int matchRank)
 		{
-			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 ();
+			if (filterLowerCase.Length == 0) {
+				matchRank = int.MinValue;
+				return true;
 			}
+			MatchLane lane = MatchString (name);
+			if (lane != null) {
+				matchRank = -(lane.Positions [0] + (name.Length - filterLowerCase.Length));
+				return true;
+			}
+			matchRank = int.MinValue;
+			return false;
 		}
 
-		public bool IsMatch (string text)
+		public bool IsMatch (string name)
 		{
-			return GetMatch (text) != null;
+			return filterLowerCase.Length == 0 || MatchString (name) != null;
 		}
 		
 		/// <summary>
@@ -71,57 +74,160 @@ namespace MonoDevelop.Ide.CodeCompletion
 		/// </param>
 		public int[] GetMatch (string text)
 		{
-			if (string.IsNullOrEmpty (filterTextUpperCase))
+			if (filterLowerCase.Length == 0) 
 				return new int[0];
-			if (string.IsNullOrEmpty (text))
+			var lane = MatchString (text);
+			if (lane == null)
 				return null;
+			int cnt = 0;
+			for (int i = 0; i < lane.Positions.Length; i++) {
+				cnt += lane.Lengths[i];
+			}
+			int[] result = new int [cnt];
+			int x = 0;
+			for (int i = 0; i < lane.Positions.Length; i++) {
+				int p = lane.Positions[i];
+				for (int j = 0 ; j < lane.Lengths[i]; j++) {
+					result[x++] = p++;
+				}
+			}
+			return result;
+		}
 
-			matchIndices.Clear ();
-			int j = 0;
+		MatchLane MatchString (string text)
+		{
+			if (text.Length < filterLowerCase.Length)
+				return null;
+	
+			matchLanes.Clear ();
+			bool lastWasSeparator = false;
+			int tn = 0;
+			char filterStart = filterLowerCase[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;
-				}
+			while (tn < text.Length) {
+				char ct = text [tn];
+				bool ctIsUpper = char.IsUpper (ct);
+				char ctLower = ctIsUpper ? char.ToLower (ct) : ct;
 				
-				// letter case
-				bool textCharIsUpper = char.IsUpper (text[j]);
-				if ((textCharIsUpper || filterTextLowerCaseTable[i]) && filterChar == (textCharIsUpper ? text[j] : char.ToUpper (text[j]))) {
-					matchIndices.Add (j++);
-					continue;
+				// Keep the lane count in a var because new lanes don't have to be updated
+				// until the next iteration
+				int laneCount = matchLanes != null ? matchLanes.Count : 0;
+	
+				if (ctLower == filterStart) {
+					matchLanes.Add (new MatchLane (MatchMode.Substring, tn, text.Length - tn));
+					if (filterLowerCase.Length == 1)
+						return matchLanes[0];
+					if (ctIsUpper || lastWasSeparator)
+						matchLanes.Add (new MatchLane (MatchMode.Acronym, tn, text.Length - tn));
 				}
-
-				// 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;
+	
+				for (int n=0; n<laneCount; n++) {
+					MatchLane lane = matchLanes [n];
+					if (lane == null)
+						continue;
+					char cm = filterLowerCase [lane.MatchIndex];
+					bool match = ctLower == cm;
+					bool wordStartMatch = match && (tn == 0 || ctIsUpper || lastWasSeparator);
+	
+					if (lane.MatchMode == MatchMode.Substring) {
+						if (wordStartMatch) {
+							// Possible acronym match after a substring. Start a new lane.
+							MatchLane newLane = lane.Clone ();
+							newLane.MatchMode = MatchMode.Acronym;
+							newLane.Index++;
+							newLane.Positions [newLane.Index] = tn;
+							newLane.Lengths [newLane.Index] = 1;
+							newLane.MatchIndex++;
+							matchLanes.Add (newLane);
+						}
+						if (match) {
+							// Maybe it is a false substring start, so add a new lane to keep
+							// track of the old lane
+							MatchLane newLane = lane.Clone ();
+							newLane.MatchMode = MatchMode.Acronym;
+							matchLanes.Add (newLane);
+	
+							// Update the current lane
+							lane.Lengths [lane.Index]++;
+							lane.MatchIndex++;
+						} else {
+							if (lane.Lengths [lane.Index] > 1)
+								lane.MatchMode = MatchMode.Acronym;
+							else
+								matchLanes [n] = null; // Kill the lane
+						}
+					}
+					else if (lane.MatchMode == MatchMode.Acronym) {
+						if (match && lane.Positions [lane.Index] == tn - 1) {
+							// Possible substring match after an acronim. Start a new lane.
+							MatchLane newLane = lane.Clone ();
+							newLane.MatchMode = MatchMode.Substring;
+							newLane.Lengths [newLane.Index]++;
+							newLane.MatchIndex++;
+							matchLanes.Add (newLane);
+							if (newLane.MatchIndex == filterLowerCase.Length)
+								return newLane;
+						}
+						if (wordStartMatch || (match && char.IsPunctuation (cm))) {
+							// Maybe it is a false acronym start, so add a new lane to keep
+							// track of the old lane
+							MatchLane newLane = lane.Clone ();
+							matchLanes.Add (newLane);
+	
+							// Update the current lane
+							lane.Index++;
+							lane.Positions [lane.Index] = tn;
+							lane.Lengths [lane.Index] = 1;
+							lane.MatchIndex++;
+						}
 					}
+					if (lane.MatchIndex == filterLowerCase.Length)
+						return lane;
 				}
-				
-				if (!wasMatch)
-					return null;
+				lastWasSeparator = (ct == '.' || ct == '_' || ct == '-' || ct == ' ' || ct == '/' || ct == '\\');
+				tn++;
+			}
+			return null;
+		}
+	
+		enum MatchMode {
+			Substring,
+			Acronym
+		}
+	
+		class MatchLane
+		{
+			public int[] Positions;
+			public int[] Lengths;
+			public MatchMode MatchMode;
+			public int Index;
+			public int MatchIndex;
+	
+			public MatchLane ()
+			{
+			}
+	
+			public MatchLane (MatchMode mode, int pos, int len)
+			{
+				MatchMode = mode;
+				Positions = new int [len];
+				Lengths = new int [len];
+				Positions [0] = pos;
+				Lengths [0] = 1;
+				Index = 0;
+				MatchIndex = 1;
+			}
+	
+			public MatchLane Clone ()
+			{
+				MatchLane lane = new MatchLane ();
+				lane.Positions = (int[]) Positions.Clone ();
+				lane.Lengths = (int[]) Lengths.Clone ();
+				lane.MatchMode = MatchMode;
+				lane.MatchIndex = MatchIndex;
+				lane.Index = Index;
+				return lane;
 			}
-			
-			return matchIndices.ToArray ();
 		}
 	}