Split sorting option. one for sorting. One to force levenshtein.

10 files changed, 38 insertions, 28 deletions

diff --git a/Changelog b/Changelog
index d4492f37..e9b8ccd5 100644
--- a/Changelog
+++ b/Changelog
@@ -1,6 +1,7 @@
 v1.4.0: (unreleased)
 	New Features:
 		- Super-{1-10} activates row 1-10. 
+		- FZF style sorting for fuzzy matching (thanks to MaskRay) (#533)
 
 v1.3.1: Dan vs. Greg: The never ending story, reloaded.
 	New Features
diff --git a/config/config.c b/config/config.c
index 7dc6e215..3bec7dec 100644
--- a/config/config.c
+++ b/config/config.c
@@ -86,6 +86,8 @@ Settings config = {
     .fixed_num_lines   = TRUE,
     /** Do not use history */
     .disable_history   = FALSE,
+    /** Sort the displayed list */
+    .sort              = FALSE,
     /** Use levenshtein sorting when matching */
     .levenshtein_sort  = FALSE,
     /** Case sensitivity of the search */
diff --git a/doc/help-output.txt b/doc/help-output.txt
index a423c11e..d1eedc2a 100644
--- a/doc/help-output.txt
+++ b/doc/help-output.txt
@@ -81,7 +81,9 @@ Global options:
 		xkill -id {window} (File)
 	-[no-]disable-history                   Disable history in run/ssh
 		False (File)
-	-[no-]levenshtein-sort                  Use levenshtein sorting
+	-[no-]sort                              Use sorting
+		False (Default)
+	-[no-]levenshtein-sort                  Use levenshtein sorting also for fuzzy matching
 		False (File)
 	-[no-]case-sensitive                    Set case-sensitivity
 		False (File)
diff --git a/doc/test_xr.txt b/doc/test_xr.txt
index d8db08e8..03e71321 100644
--- a/doc/test_xr.txt
+++ b/doc/test_xr.txt
@@ -44,7 +44,9 @@ rofi.run-shell-command:              {terminal} -e {cmd}
 rofi.window-command:                 xkill -id {window}
 ! "Disable history in run/ssh" Set from: File
 rofi.disable-history:                false
-! "Use levenshtein sorting" Set from: File
+! "Use sorting" Set from: Default
+! rofi.sort:                           false
+! "Use levenshtein sorting also for fuzzy matching" Set from: File
 rofi.levenshtein-sort:               false
 ! "Set case-sensitivity" Set from: File
 rofi.case-sensitive:                 false
diff --git a/include/helper.h b/include/helper.h
index d580c4df..01799967 100644
--- a/include/helper.h
+++ b/include/helper.h
@@ -167,13 +167,15 @@ char *rofi_expand_path ( const char *input );
 
 /**
  * @param needle The string to find match weight off
+ * @param needlelen The length of the needle
  * @param haystack The string to match against
+ * @param haystacklen The length of the haystack
  *
  * UTF-8 aware levenshtein distance calculation
  *
  * @returns the levenshtein distance between needle and haystack
  */
-unsigned int levenshtein ( const char *needle, const char *haystack );
+unsigned int levenshtein ( const char *needle, const glong needlelen, const char *haystack, const glong haystacklen );
 
 /**
  * @param data the unvalidated character array holding possible UTF-8 data
diff --git a/include/settings.h b/include/settings.h
index 344208e2..90e0be08 100644
--- a/include/settings.h
+++ b/include/settings.h
@@ -98,6 +98,8 @@ typedef struct
     unsigned int   fixed_num_lines;
     /** Do not use history */
     unsigned int   disable_history;
+    /** Toggle to enable sorting. */
+    unsigned int   sort;
     /** Use levenshtein sorting when matching */
     unsigned int   levenshtein_sort;
     /** Search case sensitivity */
diff --git a/source/helper.c b/source/helper.c
index 11073d66..72105352 100644
--- a/source/helper.c
+++ b/source/helper.c
@@ -656,10 +656,8 @@ char *rofi_expand_path ( const char *input )
 /** Return the minimum value of a,b,c */
 #define MIN3( a, b, c )    ( ( a ) < ( b ) ? ( ( a ) < ( c ) ? ( a ) : ( c ) ) : ( ( b ) < ( c ) ? ( b ) : ( c ) ) )
 
-unsigned int levenshtein ( const char *needle, const char *haystack )
+unsigned int levenshtein ( const char *needle, const glong needlelen,  const char *haystack, const glong haystacklen )
 {
-    const size_t needlelen   = g_utf8_strlen ( needle, -1 );
-    const size_t haystacklen = g_utf8_strlen ( haystack, -1 );
     unsigned int column[needlelen + 1];
     for ( unsigned int y = 0; y <= needlelen; y++ ) {
         column[y] = y;
diff --git a/source/view.c b/source/view.c
index 8b60dabc..44b555d9 100644
--- a/source/view.c
+++ b/source/view.c
@@ -140,7 +140,7 @@ void rofi_view_get_current_monitor ( int *width, int *height )
 static char * get_matching_state ( void )
 {
     if ( config.case_sensitive ) {
-        if ( config.levenshtein_sort ) {
+        if ( config.sort ) {
             return "±";
         }
         else {
@@ -148,7 +148,7 @@ static char * get_matching_state ( void )
         }
     }
     else{
-        if ( config.levenshtein_sort ) {
+        if ( config.sort ) {
             return "+";
         }
     }
@@ -545,7 +545,7 @@ static void filter_elements ( thread_state *t, G_GNUC_UNUSED gpointer user_data
 {
     char  *pattern = NULL;
     glong plen     = 0;
-    if ( config.matching_method == MM_FUZZY || config.levenshtein_sort ) {
+    if ( config.sort ) {
         pattern = mode_preprocess_input ( t->state->sw, t->state->text->text );
         plen    = g_utf8_strlen ( pattern, -1 );
     }
@@ -554,16 +554,15 @@ static void filter_elements ( thread_state *t, G_GNUC_UNUSED gpointer user_data
         // If each token was matched, add it to list.
         if ( match ) {
             t->state->line_map[t->start + t->count] = i;
-            if ( config.matching_method == MM_FUZZY ) {
-                char  *str = mode_get_completion ( t->state->sw, i );
-                glong slen = g_utf8_strlen ( str, -1 );
-                t->state->distance[i] = rofi_scorer_fuzzy_evaluate ( pattern, plen, str, slen );
-                g_free ( str );
-            }
-            else if ( config.levenshtein_sort ) {
+            if ( config.sort ) {
                 // This is inefficient, need to fix it.
                 char * str = mode_get_completion ( t->state->sw, i );
-                t->state->distance[i] = levenshtein ( pattern, str );
+                glong slen = g_utf8_strlen ( str, -1 );
+                if ( config.levenshtein_sort || config.matching_method != MM_FUZZY  ) {
+                    t->state->distance[i] = levenshtein ( pattern, plen, str, slen );
+                } else {
+                    t->state->distance[i] = rofi_scorer_fuzzy_evaluate ( pattern, plen, str, slen );
+                }
                 g_free ( str );
             }
             t->count++;
@@ -1034,7 +1033,7 @@ static void rofi_view_refilter ( RofiViewState *state )
             }
             j += states[i].count;
         }
-        if ( config.matching_method == MM_FUZZY || config.levenshtein_sort ) {
+        if ( config.sort ) {
             g_qsort_with_data ( state->line_map, j, sizeof ( int ), lev_sort, state->distance );
         }
 
@@ -1101,7 +1100,7 @@ gboolean rofi_view_trigger_action ( RofiViewState *state, KeyBindingAction actio
         menu_capture_screenshot ( );
         break;
     case TOGGLE_SORT:
-        config.levenshtein_sort = !config.levenshtein_sort;
+        config.sort             = !config.sort;
         state->refilter         = TRUE;
         textbox_text ( state->case_indicator, get_matching_state () );
         break;
diff --git a/source/xrmoptions.c b/source/xrmoptions.c
index eff1644e..85f829c7 100644
--- a/source/xrmoptions.c
+++ b/source/xrmoptions.c
@@ -137,8 +137,10 @@ static XrmOption xrmOptions[] = {
 
     { xrm_Boolean, "disable-history",   { .num  = &config.disable_history       }, NULL,
       "Disable history in run/ssh", CONFIG_DEFAULT },
+    { xrm_Boolean, "sort",              { .num  = &config.sort                  }, NULL,
+      "Use sorting",             CONFIG_DEFAULT },
     { xrm_Boolean, "levenshtein-sort",  { .num  = &config.levenshtein_sort      }, NULL,
-      "Use levenshtein sorting", CONFIG_DEFAULT },
+      "Use levenshtein sorting also for fuzzy matching", CONFIG_DEFAULT },
     { xrm_Boolean, "case-sensitive",    { .num  = &config.case_sensitive        }, NULL,
       "Set case-sensitivity", CONFIG_DEFAULT },
     { xrm_Boolean, "cycle",             { .num  = &config.cycle                 }, NULL,
diff --git a/test/helper-test.c b/test/helper-test.c
index 76fcefbb..9630d0bb 100644
--- a/test/helper-test.c
+++ b/test/helper-test.c
@@ -74,14 +74,14 @@ int main ( int argc, char ** argv )
      * tokenize
      */
 
-    TASSERT ( levenshtein ( "aap", "aap" ) == 0 );
-    TASSERT ( levenshtein ( "aap", "aap " ) == 1 );
-    TASSERT ( levenshtein ( "aap ", "aap" ) == 1 );
-    TASSERTE ( levenshtein ( "aap", "aap noot" ), 5 );
-    TASSERTE ( levenshtein ( "aap", "noot aap" ), 5 );
-    TASSERTE ( levenshtein ( "aap", "noot aap mies" ), 10 );
-    TASSERTE ( levenshtein ( "noot aap mies", "aap" ), 10 );
-    TASSERTE ( levenshtein ( "otp", "noot aap" ), 5 );
+    TASSERT ( levenshtein ( "aap", g_utf8_strlen ( "aap", -1), "aap", g_utf8_strlen ( "aap", -1) ) == 0 );
+    TASSERT ( levenshtein ( "aap", g_utf8_strlen ( "aap", -1), "aap ", g_utf8_strlen ( "aap ", -1) ) == 1 );
+    TASSERT ( levenshtein ( "aap ", g_utf8_strlen ( "aap ", -1), "aap", g_utf8_strlen ( "aap", -1) ) == 1 );
+    TASSERTE ( levenshtein ( "aap", g_utf8_strlen ( "aap", -1), "aap noot", g_utf8_strlen ( "aap noot", -1) ), 5 );
+    TASSERTE ( levenshtein ( "aap", g_utf8_strlen ( "aap", -1), "noot aap", g_utf8_strlen ( "noot aap", -1) ), 5 );
+    TASSERTE ( levenshtein ( "aap", g_utf8_strlen ( "aap", -1), "noot aap mies", g_utf8_strlen ( "noot aap mies", -1) ), 10 );
+    TASSERTE ( levenshtein ( "noot aap mies", g_utf8_strlen ( "noot aap mies", -1), "aap", g_utf8_strlen ( "aap", -1) ), 10 );
+    TASSERTE ( levenshtein ( "otp", g_utf8_strlen ( "otp", -1), "noot aap", g_utf8_strlen ( "noot aap", -1) ), 5 );
     /**
      * Quick converision check.
      */