fzy

commit f2dff48ad794a700b4868aa6e97ef5a0b31bf311
parent e16586569e6578ff1590e8ea03dba08e97379f19
Author: John Hawthorn <john.hawthorn@gmail.com>
Date:   Tue, 29 Jul 2014 21:28:32 -0700

Improve scoring

Diffstat:
M
fzytest.c
 | 
9
+++++++++
M
match.c
 | 
53
++++++++++++++++++++++++++++++++++++-----------------

2 files changed, 45 insertions(+), 17 deletions(-)
diff --git a/fzytest.c b/fzytest.c
@@ -35,6 +35,15 @@ int test_scoring(){
 	/* App/MOdels/foo is better than App/M/fOo  */
 	assert(match("amo", "app/m/foo") < match("amo", "app/models/foo"));
 
+	/* GEMFIle.Lock < GEMFILe  */
+	assert(match("gemfil", "Gemfile.lock") < match("gemfil", "Gemfile"));
+
+	/* GEMFIle.Lock < GEMFILe  */
+	assert(match("gemfil", "Gemfile.lock") < match("gemfil", "Gemfile"));
+
+	/* Prefer shorter matches */
+	assert(match("test", "tests") > match("test", "testing"));
+
 	return 0;
 }
 
diff --git a/match.c b/match.c
@@ -3,6 +3,7 @@
 #include <strings.h>
 #include <stdio.h>
 #include <float.h>
+#include <math.h>
 
 #include "fzy.h"
 
@@ -18,8 +19,8 @@ int has_match(const char *needle, const char *haystack){
 
 #define max(a, b) (((a) > (b)) ? (a) : (b))
 typedef double score_t;
-#define SCORE_MAX DBL_MAX
-#define SCORE_MIN -DBL_MAX
+#define SCORE_MAX INFINITY
+#define SCORE_MIN -INFINITY
 
 /* print one of the internal matrices */
 void mat_print(score_t *mat, int n, int m){
@@ -65,34 +66,52 @@ double calculate_score(const char *needle, const char *haystack, size_t *positio
 	 */
 
 	/* Which positions are beginning of words */
-	int at_bow = 1;
 	char last_ch = '\0';
 	for(int i = 0; i < m; i++){
 		char ch = haystack[i];
-		/* TODO: What about allcaps (ex. README) */
-		int bow = (at_bow && isalnum(ch)) || (isupper(ch) && !isupper(last_ch));
-		at_bow = !isalnum(ch);
-		last_ch = ch;
 
-		match_bonus[i] = bow ? 1.5 : 0;
+		score_t score = 0;
+		if(isalnum(ch)){
+			if(last_ch == '/'){
+				score = 1.5;
+			}else if(last_ch == '-' ||
+					last_ch == '_' ||
+					last_ch == ' ' ||
+					(last_ch >= '0' && last_ch <= '9')){
+				score = 1.2;
+			}else if(last_ch >= 'a' && last_ch <= 'z' &&
+					ch >= 'A' && ch <= 'Z'){
+				/* CamelCase */
+				score = 1.1;
+			}else if(last_ch == '.'){
+				score = 0.8;
+			}
+		}
+
+		match_bonus[i] = score;
+		last_ch = ch;
 	}
 
 	for(int i = 0; i < n; i++){
 		for(int j = 0; j < m; j++){
-			D[i][j] = SCORE_MIN;
+			score_t score = j ? SCORE_MIN : 0;
 			int match = tolower(needle[i]) == tolower(haystack[j]);
+			D[i][j] = SCORE_MIN;
 			if(match){
-				score_t score = 0;
 				if(i && j){
-					score = M[i-1][j-1] + match_bonus[j];
+					score = max(score, M[i-1][j-1] + match_bonus[j]);
 
 					/* consecutive match, doesn't stack with match_bonus */
-					score = max(score, 1 + D[i-1][j-1]);
+					score = max(score, D[i-1][j-1] + 1.0);
+				}else if(!i){
+					score = (j * -0.01) + match_bonus[j];
 				}
-				M[i][j] = D[i][j] = score;
+				D[i][j] = score;
+			}
+			if(j){
+				score = max(score, M[i][j-1] - 0.01);
 			}
-			if(j)
-				M[i][j] = max(M[i][j], M[i][j-1] - 0.05);
+			M[i][j] = score;
 		}
 	}
 
@@ -113,8 +132,8 @@ double calculate_score(const char *needle, const char *haystack, size_t *positio
 				 * we encounter, the latest in the candidate
 				 * string.
 				 */
-				if(D[i][j] == M[i][j]){
-					positions[i] = j;
+				if(tolower(needle[i]) == tolower(haystack[j]) && D[i][j] == M[i][j]){
+					positions[i] = j--;
 					break;
 				}
 			}