To: vim_dev@googlegroups.com
Subject: Patch 8.2.1893
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------

Patch 8.2.1893
Problem:    Fuzzy matching does not support multiple words.
Solution:   Add support for matching white space separated words. (Yegappan
            Lakshmanan, closes #7163)
Files:      runtime/doc/eval.txt, src/search.c,
            src/testdir/test_matchfuzzy.vim


*** ../vim-8.2.1892/runtime/doc/eval.txt	2020-10-03 20:16:48.771216676 +0200
--- runtime/doc/eval.txt	2020-10-23 16:47:10.528682900 +0200
***************
*** 7145,7150 ****
--- 7210,7219 ----
  		The 'ignorecase' option is used to set the ignore-caseness of
  		the pattern.  'smartcase' is NOT used.  The matching is always
  		done like 'magic' is set and 'cpoptions' is empty.
+ 		Note that a match at the start is preferred, thus when the
+ 		pattern is using "*" (any number of matches) it tends to find
+ 		zero matches at the start instead of a number of matches
+ 		further down in the text.
  
  		Can also be used as a |method|: >
  			GetList()->match('word')
***************
*** 7298,7305 ****
  		the strings in {list} that fuzzy match {str}. The strings in
  		the returned list are sorted based on the matching score.
  
  		If {list} is a list of dictionaries, then the optional {dict}
! 		argument supports the following items:
  		    key		key of the item which is fuzzy matched against
  				{str}. The value of this item should be a
  				string.
--- 7367,7381 ----
  		the strings in {list} that fuzzy match {str}. The strings in
  		the returned list are sorted based on the matching score.
  
+ 		The optional {dict} argument always supports the following
+ 		items:
+ 		    matchseq	When this item is present and {str} contains
+ 				multiple words separated by white space, then
+ 				returns only matches that contain the words in
+ 				the given sequence.
+ 
  		If {list} is a list of dictionaries, then the optional {dict}
! 		argument supports the following additional items:
  		    key		key of the item which is fuzzy matched against
  				{str}. The value of this item should be a
  				string.
***************
*** 7313,7318 ****
--- 7389,7397 ----
  		matching is NOT supported.  The maximum supported {str} length
  		is 256.
  
+ 		When {str} has multiple words each separated by white space,
+ 		then the list of strings that have all the words is returned.
+ 
  		If there are no matching strings or there is an error, then an
  		empty list is returned. If length of {str} is greater than
  		256, then returns an empty list.
***************
*** 7332,7338 ****
  		   :echo v:oldfiles->matchfuzzy("test")
  <		results in a list of file names fuzzy matching "test". >
  		   :let l = readfile("buffer.c")->matchfuzzy("str")
! <		results in a list of lines in "buffer.c" fuzzy matching "str".
  
  matchfuzzypos({list}, {str} [, {dict}])			*matchfuzzypos()*
  		Same as |matchfuzzy()|, but returns the list of matched
--- 7411,7422 ----
  		   :echo v:oldfiles->matchfuzzy("test")
  <		results in a list of file names fuzzy matching "test". >
  		   :let l = readfile("buffer.c")->matchfuzzy("str")
! <		results in a list of lines in "buffer.c" fuzzy matching "str". >
! 		   :echo ['one two', 'two one']->matchfuzzy('two one')
! <		results in ['two one', 'one two']. >
! 		   :echo ['one two', 'two one']->matchfuzzy('two one',
! 						\ {'matchseq': 1})
! <		results in ['two one'].
  
  matchfuzzypos({list}, {str} [, {dict}])			*matchfuzzypos()*
  		Same as |matchfuzzy()|, but returns the list of matched
*** ../vim-8.2.1892/src/search.c	2020-10-20 19:01:26.574305119 +0200
--- src/search.c	2020-10-23 16:43:18.685306586 +0200
***************
*** 4203,4218 ****
   * Ported from the lib_fts library authored by Forrest Smith.
   * https://github.com/forrestthewoods/lib_fts/tree/master/code
   *
!  * Blog describing the algorithm:
   * https://www.forrestthewoods.com/blog/reverse_engineering_sublime_texts_fuzzy_match/
   *
   * Each matching string is assigned a score. The following factors are checked:
!  *   Matched letter
!  *   Unmatched letter
!  *   Consecutively matched letters
!  *   Proximity to start
!  *   Letter following a separator (space, underscore)
!  *   Uppercase letter following lowercase (aka CamelCase)
   *
   * Matched letters are good. Unmatched letters are bad. Matching near the start
   * is good. Matching the first letter in the middle of a phrase is good.
--- 4203,4218 ----
   * Ported from the lib_fts library authored by Forrest Smith.
   * https://github.com/forrestthewoods/lib_fts/tree/master/code
   *
!  * The following blog describes the fuzzy matching algorithm:
   * https://www.forrestthewoods.com/blog/reverse_engineering_sublime_texts_fuzzy_match/
   *
   * Each matching string is assigned a score. The following factors are checked:
!  *   - Matched letter
!  *   - Unmatched letter
!  *   - Consecutively matched letters
!  *   - Proximity to start
!  *   - Letter following a separator (space, underscore)
!  *   - Uppercase letter following lowercase (aka CamelCase)
   *
   * Matched letters are good. Unmatched letters are bad. Matching near the start
   * is good. Matching the first letter in the middle of a phrase is good.
***************
*** 4222,4237 ****
   * File paths are different from file names. File extensions may be ignorable.
   * Single words care about consecutive matches but not separators or camel
   * case.
!  *   Score starts at 0
   *   Matched letter: +0 points
   *   Unmatched letter: -1 point
!  *   Consecutive match bonus: +5 points
!  *   Separator bonus: +10 points
!  *   Camel case bonus: +10 points
!  *   Unmatched leading letter: -3 points (max: -9)
   *
   * There is some nuance to this. Scores don’t have an intrinsic meaning. The
!  * score range isn’t 0 to 100. It’s roughly [-50, 50]. Longer words have a
   * lower minimum score due to unmatched letter penalty. Longer search patterns
   * have a higher maximum score due to match bonuses.
   *
--- 4222,4238 ----
   * File paths are different from file names. File extensions may be ignorable.
   * Single words care about consecutive matches but not separators or camel
   * case.
!  *   Score starts at 100
   *   Matched letter: +0 points
   *   Unmatched letter: -1 point
!  *   Consecutive match bonus: +15 points
!  *   First letter bonus: +15 points
!  *   Separator bonus: +30 points
!  *   Camel case bonus: +30 points
!  *   Unmatched leading letter: -5 points (max: -15)
   *
   * There is some nuance to this. Scores don’t have an intrinsic meaning. The
!  * score range isn’t 0 to 100. It’s roughly [50, 150]. Longer words have a
   * lower minimum score due to unmatched letter penalty. Longer search patterns
   * have a higher maximum score due to match bonuses.
   *
***************
*** 4247,4252 ****
--- 4248,4254 ----
   */
  typedef struct
  {
+     int		idx;		// used for stable sort
      listitem_T	*item;
      int		score;
      list_T	*lmatchpos;
***************
*** 4267,4272 ****
--- 4269,4276 ----
  #define MAX_LEADING_LETTER_PENALTY -15
  // penalty for every letter that doesn't match
  #define UNMATCHED_LETTER_PENALTY -1
+ // penalty for gap in matching positions (-2 * k)
+ #define GAP_PENALTY	-2
  // Score for a string that doesn't fuzzy match the pattern
  #define SCORE_NONE	-9999
  
***************
*** 4319,4324 ****
--- 4323,4330 ----
  	    // Sequential
  	    if (currIdx == (prevIdx + 1))
  		score += SEQUENTIAL_BONUS;
+ 	    else
+ 		score += GAP_PENALTY * (currIdx - prevIdx);
  	}
  
  	// Check for bonuses based on neighbor character value
***************
*** 4334,4340 ****
  		while (sidx < currIdx)
  		{
  		    neighbor = (*mb_ptr2char)(p);
! 		    (void)mb_ptr2char_adv(&p);
  		    sidx++;
  		}
  		curr = (*mb_ptr2char)(p);
--- 4340,4346 ----
  		while (sidx < currIdx)
  		{
  		    neighbor = (*mb_ptr2char)(p);
! 		    MB_PTR_ADV(p);
  		    sidx++;
  		}
  		curr = (*mb_ptr2char)(p);
***************
*** 4362,4367 ****
--- 4368,4377 ----
      return score;
  }
  
+ /*
+  * Perform a recursive search for fuzzy matching 'fuzpat' in 'str'.
+  * Return the number of matching characters.
+  */
      static int
  fuzzy_match_recursive(
  	char_u		*fuzpat,
***************
*** 4386,4396 ****
      // Count recursions
      ++*recursionCount;
      if (*recursionCount >= FUZZY_MATCH_RECURSION_LIMIT)
! 	return FALSE;
  
      // Detect end of strings
      if (*fuzpat == '\0' || *str == '\0')
! 	return FALSE;
  
      // Loop through fuzpat and str looking for a match
      first_match = TRUE;
--- 4396,4406 ----
      // Count recursions
      ++*recursionCount;
      if (*recursionCount >= FUZZY_MATCH_RECURSION_LIMIT)
! 	return 0;
  
      // Detect end of strings
      if (*fuzpat == '\0' || *str == '\0')
! 	return 0;
  
      // Loop through fuzpat and str looking for a match
      first_match = TRUE;
***************
*** 4411,4417 ****
  
  	    // Supplied matches buffer was too short
  	    if (nextMatch >= maxMatches)
! 		return FALSE;
  
  	    // "Copy-on-Write" srcMatches into matches
  	    if (first_match && srcMatches)
--- 4421,4427 ----
  
  	    // Supplied matches buffer was too short
  	    if (nextMatch >= maxMatches)
! 		return 0;
  
  	    // "Copy-on-Write" srcMatches into matches
  	    if (first_match && srcMatches)
***************
*** 4444,4455 ****
  	    // Advance
  	    matches[nextMatch++] = strIdx;
  	    if (has_mbyte)
! 		(void)mb_ptr2char_adv(&fuzpat);
  	    else
  		++fuzpat;
  	}
  	if (has_mbyte)
! 	    (void)mb_ptr2char_adv(&str);
  	else
  	    ++str;
  	strIdx++;
--- 4454,4465 ----
  	    // Advance
  	    matches[nextMatch++] = strIdx;
  	    if (has_mbyte)
! 		MB_PTR_ADV(fuzpat);
  	    else
  		++fuzpat;
  	}
  	if (has_mbyte)
! 	    MB_PTR_ADV(str);
  	else
  	    ++str;
  	strIdx++;
***************
*** 4469,4480 ****
  	// Recursive score is better than "this"
  	memcpy(matches, bestRecursiveMatches, maxMatches * sizeof(matches[0]));
  	*outScore = bestRecursiveScore;
! 	return TRUE;
      }
      else if (matched)
! 	return TRUE;		// "this" score is better than recursive
  
!     return FALSE;		// no match
  }
  
  /*
--- 4479,4490 ----
  	// Recursive score is better than "this"
  	memcpy(matches, bestRecursiveMatches, maxMatches * sizeof(matches[0]));
  	*outScore = bestRecursiveScore;
! 	return nextMatch;
      }
      else if (matched)
! 	return nextMatch;	// "this" score is better than recursive
  
!     return 0;		// no match
  }
  
  /*
***************
*** 4485,4529 ****
   * Scores values have no intrinsic meaning.  Possible score range is not
   * normalized and varies with pattern.
   * Recursion is limited internally (default=10) to prevent degenerate cases
!  * (fuzpat="aaaaaa" str="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa").
   * Uses char_u for match indices. Therefore patterns are limited to MAXMATCHES
   * characters.
   *
!  * Returns TRUE if 'fuzpat' matches 'str'. Also returns the match score in
   * 'outScore' and the matching character positions in 'matches'.
   */
      static int
  fuzzy_match(
  	char_u		*str,
! 	char_u		*fuzpat,
  	int		*outScore,
  	matchidx_T	*matches,
  	int		maxMatches)
  {
      int		recursionCount = 0;
      int		len = MB_CHARLEN(str);
  
      *outScore = 0;
  
!     return fuzzy_match_recursive(fuzpat, str, 0, outScore, str, len, NULL,
! 	    matches, maxMatches, 0, &recursionCount);
  }
  
  /*
   * Sort the fuzzy matches in the descending order of the match score.
   */
      static int
! fuzzy_item_compare(const void *s1, const void *s2)
  {
      int		v1 = ((fuzzyItem_T *)s1)->score;
      int		v2 = ((fuzzyItem_T *)s2)->score;
  
!     return v1 == v2 ? 0 : v1 > v2 ? -1 : 1;
  }
  
  /*
   * Fuzzy search the string 'str' in a list of 'items' and return the matching
   * strings in 'fmatchlist'.
   * If 'items' is a list of strings, then search for 'str' in the list.
   * If 'items' is a list of dicts, then either use 'key' to lookup the string
   * for each item or use 'item_cb' Funcref function to get the string.
--- 4495,4604 ----
   * Scores values have no intrinsic meaning.  Possible score range is not
   * normalized and varies with pattern.
   * Recursion is limited internally (default=10) to prevent degenerate cases
!  * (pat_arg="aaaaaa" str="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa").
   * Uses char_u for match indices. Therefore patterns are limited to MAXMATCHES
   * characters.
   *
!  * Returns TRUE if 'pat_arg' matches 'str'. Also returns the match score in
   * 'outScore' and the matching character positions in 'matches'.
   */
      static int
  fuzzy_match(
  	char_u		*str,
! 	char_u		*pat_arg,
! 	int		matchseq,
  	int		*outScore,
  	matchidx_T	*matches,
  	int		maxMatches)
  {
      int		recursionCount = 0;
      int		len = MB_CHARLEN(str);
+     char_u	*save_pat;
+     char_u	*pat;
+     char_u	*p;
+     int		complete = FALSE;
+     int		score = 0;
+     int		numMatches = 0;
+     int		matchCount;
  
      *outScore = 0;
  
!     save_pat = vim_strsave(pat_arg);
!     if (save_pat == NULL)
! 	return FALSE;
!     pat = save_pat;
!     p = pat;
! 
!     // Try matching each word in 'pat_arg' in 'str'
!     while (TRUE)
!     {
! 	if (matchseq)
! 	    complete = TRUE;
! 	else
! 	{
! 	    // Extract one word from the pattern (separated by space)
! 	    p = skipwhite(p);
! 	    if (*p == NUL)
! 		break;
! 	    pat = p;
! 	    while (*p != NUL && !VIM_ISWHITE(PTR2CHAR(p)))
! 	    {
! 		if (has_mbyte)
! 		    MB_PTR_ADV(p);
! 		else
! 		    ++p;
! 	    }
! 	    if (*p == NUL)		// processed all the words
! 		complete = TRUE;
! 	    *p = NUL;
! 	}
! 
! 	score = 0;
! 	recursionCount = 0;
! 	matchCount = fuzzy_match_recursive(pat, str, 0, &score, str, len, NULL,
! 				matches + numMatches, maxMatches - numMatches,
! 				0, &recursionCount);
! 	if (matchCount == 0)
! 	{
! 	    numMatches = 0;
! 	    break;
! 	}
! 
! 	// Accumulate the match score and the number of matches
! 	*outScore += score;
! 	numMatches += matchCount;
! 
! 	if (complete)
! 	    break;
! 
! 	// try matching the next word
! 	++p;
!     }
! 
!     vim_free(save_pat);
!     return numMatches != 0;
  }
  
  /*
   * Sort the fuzzy matches in the descending order of the match score.
+  * For items with same score, retain the order using the index (stable sort)
   */
      static int
! fuzzy_match_item_compare(const void *s1, const void *s2)
  {
      int		v1 = ((fuzzyItem_T *)s1)->score;
      int		v2 = ((fuzzyItem_T *)s2)->score;
+     int		idx1 = ((fuzzyItem_T *)s1)->idx;
+     int		idx2 = ((fuzzyItem_T *)s2)->idx;
  
!     return v1 == v2 ? (idx1 - idx2) : v1 > v2 ? -1 : 1;
  }
  
  /*
   * Fuzzy search the string 'str' in a list of 'items' and return the matching
   * strings in 'fmatchlist'.
+  * If 'matchseq' is TRUE, then for multi-word search strings, match all the
+  * words in sequence.
   * If 'items' is a list of strings, then search for 'str' in the list.
   * If 'items' is a list of dicts, then either use 'key' to lookup the string
   * for each item or use 'item_cb' Funcref function to get the string.
***************
*** 4531,4539 ****
   * matches for each item.
   */
      static void
! match_fuzzy(
  	list_T		*items,
  	char_u		*str,
  	char_u		*key,
  	callback_T	*item_cb,
  	int		retmatchpos,
--- 4606,4615 ----
   * matches for each item.
   */
      static void
! fuzzy_match_in_list(
  	list_T		*items,
  	char_u		*str,
+ 	int		matchseq,
  	char_u		*key,
  	callback_T	*item_cb,
  	int		retmatchpos,
***************
*** 4561,4566 ****
--- 4637,4643 ----
  	char_u		*itemstr;
  	typval_T	rettv;
  
+ 	ptrs[i].idx = i;
  	ptrs[i].item = li;
  	ptrs[i].score = SCORE_NONE;
  	itemstr = NULL;
***************
*** 4593,4617 ****
  	}
  
  	if (itemstr != NULL
! 		&& fuzzy_match(itemstr, str, &score, matches,
  		    sizeof(matches) / sizeof(matches[0])))
  	{
  	    // Copy the list of matching positions in itemstr to a list, if
  	    // 'retmatchpos' is set.
  	    if (retmatchpos)
  	    {
! 		int	j;
! 		int	strsz;
  
  		ptrs[i].lmatchpos = list_alloc();
  		if (ptrs[i].lmatchpos == NULL)
  		    goto done;
! 		strsz = MB_CHARLEN(str);
! 		for (j = 0; j < strsz; j++)
  		{
! 		    if (list_append_number(ptrs[i].lmatchpos,
! 				matches[j]) == FAIL)
! 			goto done;
  		}
  	    }
  	    ptrs[i].score = score;
--- 4670,4703 ----
  	}
  
  	if (itemstr != NULL
! 		&& fuzzy_match(itemstr, str, matchseq, &score, matches,
  		    sizeof(matches) / sizeof(matches[0])))
  	{
  	    // Copy the list of matching positions in itemstr to a list, if
  	    // 'retmatchpos' is set.
  	    if (retmatchpos)
  	    {
! 		int	j = 0;
! 		char_u	*p;
  
  		ptrs[i].lmatchpos = list_alloc();
  		if (ptrs[i].lmatchpos == NULL)
  		    goto done;
! 
! 		p = str;
! 		while (*p != NUL)
  		{
! 		    if (!VIM_ISWHITE(PTR2CHAR(p)))
! 		    {
! 			if (list_append_number(ptrs[i].lmatchpos,
! 				    matches[j]) == FAIL)
! 			    goto done;
! 			j++;
! 		    }
! 		    if (has_mbyte)
! 			MB_PTR_ADV(p);
! 		    else
! 			++p;
  		}
  	    }
  	    ptrs[i].score = score;
***************
*** 4627,4633 ****
  
  	// Sort the list by the descending order of the match score
  	qsort((void *)ptrs, (size_t)len, sizeof(fuzzyItem_T),
! 		fuzzy_item_compare);
  
  	// For matchfuzzy(), return a list of matched strings.
  	//	    ['str1', 'str2', 'str3']
--- 4713,4719 ----
  
  	// Sort the list by the descending order of the match score
  	qsort((void *)ptrs, (size_t)len, sizeof(fuzzyItem_T),
! 		fuzzy_match_item_compare);
  
  	// For matchfuzzy(), return a list of matched strings.
  	//	    ['str1', 'str2', 'str3']
***************
*** 4687,4692 ****
--- 4773,4779 ----
      callback_T	cb;
      char_u	*key = NULL;
      int		ret;
+     int		matchseq = FALSE;
  
      CLEAR_POINTER(&cb);
  
***************
*** 4737,4742 ****
--- 4824,4831 ----
  		return;
  	    }
  	}
+ 	if ((di = dict_find(d, (char_u *)"matchseq", -1)) != NULL)
+ 	    matchseq = TRUE;
      }
  
      // get the fuzzy matches
***************
*** 4762,4769 ****
  	    goto done;
      }
  
!     match_fuzzy(argvars[0].vval.v_list, tv_get_string(&argvars[1]), key,
! 	    &cb, retmatchpos, rettv->vval.v_list);
  
  done:
      free_callback(&cb);
--- 4851,4858 ----
  	    goto done;
      }
  
!     fuzzy_match_in_list(argvars[0].vval.v_list, tv_get_string(&argvars[1]),
! 	    matchseq, key, &cb, retmatchpos, rettv->vval.v_list);
  
  done:
      free_callback(&cb);
*** ../vim-8.2.1892/src/testdir/test_matchfuzzy.vim	2020-10-20 19:01:26.574305119 +0200
--- src/testdir/test_matchfuzzy.vim	2020-10-23 16:43:18.685306586 +0200
***************
*** 22,37 ****
    call assert_equal(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], matchfuzzy(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], 'aa'))
    call assert_equal(256, matchfuzzy([repeat('a', 256)], repeat('a', 256))[0]->len())
    call assert_equal([], matchfuzzy([repeat('a', 300)], repeat('a', 257)))
  
    " Tests for match preferences
    " preference for camel case match
    call assert_equal(['oneTwo', 'onetwo'], ['onetwo', 'oneTwo']->matchfuzzy('onetwo'))
    " preference for match after a separator (_ or space)
!   if has("win32")
!     call assert_equal(['onetwo', 'one two', 'one_two'], ['onetwo', 'one_two', 'one two']->matchfuzzy('onetwo'))
!   else
!     call assert_equal(['onetwo', 'one_two', 'one two'], ['onetwo', 'one_two', 'one two']->matchfuzzy('onetwo'))
!   endif
    " preference for leading letter match
    call assert_equal(['onetwo', 'xonetwo'], ['xonetwo', 'onetwo']->matchfuzzy('onetwo'))
    " preference for sequential match
--- 22,36 ----
    call assert_equal(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], matchfuzzy(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], 'aa'))
    call assert_equal(256, matchfuzzy([repeat('a', 256)], repeat('a', 256))[0]->len())
    call assert_equal([], matchfuzzy([repeat('a', 300)], repeat('a', 257)))
+   " matches with same score should not be reordered
+   let l = ['abc1', 'abc2', 'abc3']
+   call assert_equal(l, l->matchfuzzy('abc'))
  
    " Tests for match preferences
    " preference for camel case match
    call assert_equal(['oneTwo', 'onetwo'], ['onetwo', 'oneTwo']->matchfuzzy('onetwo'))
    " preference for match after a separator (_ or space)
!   call assert_equal(['onetwo', 'one_two', 'one two'], ['onetwo', 'one_two', 'one two']->matchfuzzy('onetwo'))
    " preference for leading letter match
    call assert_equal(['onetwo', 'xonetwo'], ['xonetwo', 'onetwo']->matchfuzzy('onetwo'))
    " preference for sequential match
***************
*** 42,47 ****
--- 41,57 ----
    call assert_equal(['one', 'onex', 'onexx'], ['onexx', 'one', 'onex']->matchfuzzy('one'))
    " prefer complete matches over separator matches
    call assert_equal(['.vim/vimrc', '.vim/vimrc_colors', '.vim/v_i_m_r_c'], ['.vim/vimrc', '.vim/vimrc_colors', '.vim/v_i_m_r_c']->matchfuzzy('vimrc'))
+   " gap penalty
+   call assert_equal(['xxayybxxxx', 'xxayyybxxx', 'xxayyyybxx'], ['xxayyyybxx', 'xxayyybxxx', 'xxayybxxxx']->matchfuzzy('ab'))
+ 
+   " match multiple words (separated by space)
+   call assert_equal(['foo bar baz'], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzy('baz foo'))
+   call assert_equal([], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzy('one two'))
+   call assert_equal([], ['foo bar']->matchfuzzy(" \t "))
+ 
+   " test for matching a sequence of words
+   call assert_equal(['bar foo'], ['foo bar', 'bar foo', 'foobar', 'barfoo']->matchfuzzy('bar foo', {'matchseq' : 1}))
+   call assert_equal([#{text: 'two one'}], [#{text: 'one two'}, #{text: 'two one'}]->matchfuzzy('two one', #{key: 'text', matchseq: v:true}))
  
    %bw!
    eval ['somebuf', 'anotherone', 'needle', 'yetanotherone']->map({_, v -> bufadd(v) + bufload(v)})
***************
*** 49,54 ****
--- 59,65 ----
    call assert_equal(1, len(l))
    call assert_match('needle', l[0])
  
+   " Test for fuzzy matching dicts
    let l = [{'id' : 5, 'val' : 'crayon'}, {'id' : 6, 'val' : 'camera'}]
    call assert_equal([{'id' : 6, 'val' : 'camera'}], matchfuzzy(l, 'cam', {'text_cb' : {v -> v.val}}))
    call assert_equal([{'id' : 6, 'val' : 'camera'}], matchfuzzy(l, 'cam', {'key' : 'val'}))
***************
*** 64,69 ****
--- 75,83 ----
    call assert_fails("let x = matchfuzzy(l, 'cam', test_null_dict())", 'E715:')
    call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : test_null_string()})", 'E475:')
    call assert_fails("let x = matchfuzzy(l, 'foo', {'text_cb' : test_null_function()})", 'E475:')
+   " matches with same score should not be reordered
+   let l = [#{text: 'abc', id: 1}, #{text: 'abc', id: 2}, #{text: 'abc', id: 3}]
+   call assert_equal(l, l->matchfuzzy('abc', #{key: 'text'}))
  
    let l = [{'id' : 5, 'name' : 'foo'}, {'id' : 6, 'name' : []}, {'id' : 7}]
    call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : 'name'})", 'E730:')
***************
*** 75,81 ****
    let &encoding = save_enc
  endfunc
  
! " Test for the fuzzymatchpos() function
  func Test_matchfuzzypos()
    call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'curl'], 'rl'))
    call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'one', 'curl'], 'rl'))
--- 89,95 ----
    let &encoding = save_enc
  endfunc
  
! " Test for the matchfuzzypos() function
  func Test_matchfuzzypos()
    call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'curl'], 'rl'))
    call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'one', 'curl'], 'rl'))
***************
*** 83,88 ****
--- 97,106 ----
          \ [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]],
          \ matchfuzzypos(['hello world hello world', 'hello', 'world'], 'hello'))
    call assert_equal([['aaaaaaa'], [[0, 1, 2]]], matchfuzzypos(['aaaaaaa'], 'aaa'))
+   call assert_equal([['a  b'], [[0, 3]]], matchfuzzypos(['a  b'], 'a  b'))
+   call assert_equal([['a  b'], [[0, 3]]], matchfuzzypos(['a  b'], 'a    b'))
+   call assert_equal([['a  b'], [[0]]], matchfuzzypos(['a  b'], '  a  '))
+   call assert_equal([[], []], matchfuzzypos(['a  b'], '  '))
    call assert_equal([[], []], matchfuzzypos(['world', 'curl'], 'ab'))
    let x = matchfuzzypos([repeat('a', 256)], repeat('a', 256))
    call assert_equal(range(256), x[1][0])
***************
*** 104,109 ****
--- 122,133 ----
    " best recursive match
    call assert_equal([['xoone'], [[2, 3, 4]]], matchfuzzypos(['xoone'], 'one'))
  
+   " match multiple words (separated by space)
+   call assert_equal([['foo bar baz'], [[8, 9, 10, 0, 1, 2]]], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('baz foo'))
+   call assert_equal([[], []], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('one two'))
+   call assert_equal([[], []], ['foo bar']->matchfuzzypos(" \t "))
+   call assert_equal([['grace'], [[1, 2, 3, 4, 2, 3, 4, 0, 1, 2, 3, 4]]], ['grace']->matchfuzzypos('race ace grace'))
+ 
    let l = [{'id' : 5, 'val' : 'crayon'}, {'id' : 6, 'val' : 'camera'}]
    call assert_equal([[{'id' : 6, 'val' : 'camera'}], [[0, 1, 2]]],
          \ matchfuzzypos(l, 'cam', {'text_cb' : {v -> v.val}}))
***************
*** 126,131 ****
--- 150,156 ----
    call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : 'name'})", 'E730:')
  endfunc
  
+ " Test for matchfuzzy() with multibyte characters
  func Test_matchfuzzy_mbyte()
    CheckFeature multi_lang
    call assert_equal(['ンヹㄇヺヴ'], matchfuzzy(['ンヹㄇヺヴ'], 'ヹヺ'))
***************
*** 136,154 ****
    call assert_equal(['ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ', 'πbπ'],
          \ matchfuzzy(['πbπ', 'ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ'], 'ππ'))
  
    " preference for camel case match
    call assert_equal(['oneĄwo', 'oneąwo'],
          \ ['oneąwo', 'oneĄwo']->matchfuzzy('oneąwo'))
    " preference for complete match then match after separator (_ or space)
!   if has("win32")
!     " order is different between Windows and Unix :(
!     " It's important that the complete match is first
!     call assert_equal(['ⅠⅡabㄟㄠ', 'ⅠⅡa bㄟㄠ', 'ⅠⅡa_bㄟㄠ'],
!           \ ['ⅠⅡabㄟㄠ', 'ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ']->matchfuzzy('ⅠⅡabㄟㄠ'))
!   else
!     call assert_equal(['ⅠⅡabㄟㄠ'] + sort(['ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ']),
            \ ['ⅠⅡabㄟㄠ', 'ⅠⅡa bㄟㄠ', 'ⅠⅡa_bㄟㄠ']->matchfuzzy('ⅠⅡabㄟㄠ'))
!   endif
    " preference for leading letter match
    call assert_equal(['ŗŝţũŵż', 'xŗŝţũŵż'],
          \ ['xŗŝţũŵż', 'ŗŝţũŵż']->matchfuzzy('ŗŝţũŵż'))
--- 161,179 ----
    call assert_equal(['ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ', 'πbπ'],
          \ matchfuzzy(['πbπ', 'ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ'], 'ππ'))
  
+   " match multiple words (separated by space)
+   call assert_equal(['세 마리의 작은 돼지'], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzy('돼지 마리의'))
+   call assert_equal([], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzy('파란 하늘'))
+ 
    " preference for camel case match
    call assert_equal(['oneĄwo', 'oneąwo'],
          \ ['oneąwo', 'oneĄwo']->matchfuzzy('oneąwo'))
    " preference for complete match then match after separator (_ or space)
!   call assert_equal(['ⅠⅡabㄟㄠ'] + sort(['ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ']),
            \ ['ⅠⅡabㄟㄠ', 'ⅠⅡa bㄟㄠ', 'ⅠⅡa_bㄟㄠ']->matchfuzzy('ⅠⅡabㄟㄠ'))
!   " preference for match after a separator (_ or space)
!   call assert_equal(['ㄓㄔabㄟㄠ', 'ㄓㄔa_bㄟㄠ', 'ㄓㄔa bㄟㄠ'],
!         \ ['ㄓㄔa_bㄟㄠ', 'ㄓㄔa bㄟㄠ', 'ㄓㄔabㄟㄠ']->matchfuzzy('ㄓㄔabㄟㄠ'))
    " preference for leading letter match
    call assert_equal(['ŗŝţũŵż', 'xŗŝţũŵż'],
          \ ['xŗŝţũŵż', 'ŗŝţũŵż']->matchfuzzy('ŗŝţũŵż'))
***************
*** 163,168 ****
--- 188,194 ----
          \ ['ŗŝţxx', 'ŗŝţ', 'ŗŝţx']->matchfuzzy('ŗŝţ'))
  endfunc
  
+ " Test for matchfuzzypos() with multibyte characters
  func Test_matchfuzzypos_mbyte()
    CheckFeature multi_lang
    call assert_equal([['こんにちは世界'], [[0, 1, 2, 3, 4]]],
***************
*** 183,191 ****
    call assert_equal(range(256), x[1][0])
    call assert_equal([[], []], matchfuzzypos([repeat('✓', 300)], repeat('✓', 257)))
  
    " match in a long string
!   call assert_equal([[repeat('♪', 300) .. '✗✗✗'], [[300, 301, 302]]],
!         \ matchfuzzypos([repeat('♪', 300) .. '✗✗✗'], '✗✗✗'))
    " preference for camel case match
    call assert_equal([['xѳѵҁxxѳѴҁ'], [[6, 7, 8]]], matchfuzzypos(['xѳѵҁxxѳѴҁ'], 'ѳѵҁ'))
    " preference for match after a separator (_ or space)
--- 209,221 ----
    call assert_equal(range(256), x[1][0])
    call assert_equal([[], []], matchfuzzypos([repeat('✓', 300)], repeat('✓', 257)))
  
+   " match multiple words (separated by space)
+   call assert_equal([['세 마리의 작은 돼지'], [[9, 10, 2, 3, 4]]], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzypos('돼지 마리의'))
+   call assert_equal([[], []], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzypos('파란 하늘'))
+ 
    " match in a long string
!   call assert_equal([[repeat('ぶ', 300) .. 'ẼẼẼ'], [[300, 301, 302]]],
!         \ matchfuzzypos([repeat('ぶ', 300) .. 'ẼẼẼ'], 'ẼẼẼ'))
    " preference for camel case match
    call assert_equal([['xѳѵҁxxѳѴҁ'], [[6, 7, 8]]], matchfuzzypos(['xѳѵҁxxѳѴҁ'], 'ѳѵҁ'))
    " preference for match after a separator (_ or space)
*** ../vim-8.2.1892/src/version.c	2020-10-23 15:40:35.651287923 +0200
--- src/version.c	2020-10-23 16:44:37.557093291 +0200
***************
*** 752,753 ****
--- 752,755 ----
  {   /* Add new patch number below this line */
+ /**/
+     1893,
  /**/

-- 
"A clear conscience is usually the sign of a bad memory."
                             -- Steven Wright

 /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\  an exciting new programming language -- http://www.Zimbu.org        ///
 \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///