path: root/src/nvim/fuzzy.c

// fuzzy.c: fuzzy matching algorithm and related functions
//
// Portions of this file are adapted from fzy (https://github.com/jhawthorn/fzy)
// Original code:
//   Copyright (c) 2014 John Hawthorn
//   Licensed under the MIT License.
//
// 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.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "nvim/ascii_defs.h"
#include "nvim/charset.h"
#include "nvim/errors.h"
#include "nvim/eval.h"
#include "nvim/eval/typval.h"
#include "nvim/fuzzy.h"
#include "nvim/garray.h"
#include "nvim/garray_defs.h"
#include "nvim/globals.h"
#include "nvim/insexpand.h"
#include "nvim/macros_defs.h"
#include "nvim/mbyte.h"
#include "nvim/memline.h"
#include "nvim/memory.h"
#include "nvim/message.h"

typedef double score_t;

#define SCORE_MAX INFINITY
#define SCORE_MIN (-INFINITY)
#define SCORE_SCALE 1000

typedef struct {
  int idx;  ///< used for stable sort
  listitem_T *item;
  int score;
  list_T *lmatchpos;
  char *pat;
  char *itemstr;
  bool itemstr_allocated;
  int startpos;
} fuzzyItem_T;

typedef struct match_struct match_struct;

#include "fuzzy.c.generated.h"

/// fuzzy_match()
///
/// @return true if "pat_arg" matches "str". Also returns the match score in
/// "outScore" and the matching character positions in "matches".
bool fuzzy_match(char *const str, const char *const pat_arg, const bool matchseq,
                 int *const outScore, uint32_t *const matches, const int maxMatches)
  FUNC_ATTR_NONNULL_ALL
{
  bool complete = false;
  int numMatches = 0;

  *outScore = 0;

  char *const save_pat = xstrdup(pat_arg);
  char *pat = save_pat;
  char *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 && !ascii_iswhite(utf_ptr2char(p))) {
        MB_PTR_ADV(p);
      }
      if (*p == NUL) {  // processed all the words
        complete = true;
      }
      *p = NUL;
    }

    int score = FUZZY_SCORE_NONE;
    if (has_match(pat, str)) {
      score_t fzy_score = match_positions(pat, str, matches + numMatches);
      score = (fzy_score == (score_t)SCORE_MIN
               ? INT_MIN + 1
               : (fzy_score == (score_t)SCORE_MAX
                  ? INT_MAX
                  : (fzy_score < 0
                     ? (int)ceil(fzy_score * SCORE_SCALE - 0.5)
                     : (int)floor(fzy_score * SCORE_SCALE + 0.5))));
    }

    if (score == FUZZY_SCORE_NONE) {
      numMatches = 0;
      *outScore = FUZZY_SCORE_NONE;
      break;
    }

    if (score > 0 && *outScore > INT_MAX - score) {
      *outScore = INT_MAX;
    } else if (score < 0 && *outScore < INT_MIN + 1 - score) {
      *outScore = INT_MIN + 1;
    } else {
      *outScore += score;
    }

    numMatches += mb_charlen(pat);

    if (complete || numMatches >= maxMatches) {
      break;
    }

    // try matching the next word
    p++;
  }

  xfree(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 *const s1, const void *const s2)
  FUNC_ATTR_NONNULL_ALL FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_PURE
{
  const int v1 = ((const fuzzyItem_T *)s1)->score;
  const int v2 = ((const fuzzyItem_T *)s2)->score;

  if (v1 == v2) {
    const char *const pat = ((const fuzzyItem_T *)s1)->pat;
    const size_t patlen = strlen(pat);
    int startpos = ((const fuzzyItem_T *)s1)->startpos;
    const bool exact_match1 = startpos >= 0
                              && strncmp(pat, ((fuzzyItem_T *)s1)->itemstr + startpos, patlen) == 0;
    startpos = ((const fuzzyItem_T *)s2)->startpos;
    const bool exact_match2 = startpos >= 0
                              && strncmp(pat, ((fuzzyItem_T *)s2)->itemstr + startpos, patlen) == 0;

    if (exact_match1 == exact_match2) {
      const int idx1 = ((const fuzzyItem_T *)s1)->idx;
      const int idx2 = ((const fuzzyItem_T *)s2)->idx;
      return idx1 == idx2 ? 0 : idx1 > idx2 ? 1 : -1;
    } else if (exact_match2) {
      return 1;
    }
    return -1;
  } else {
    return 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.
/// If "retmatchpos" is true, then return a list of positions where "str"
/// matches for each item.
static void fuzzy_match_in_list(list_T *const l, char *const str, const bool matchseq,
                                const char *const key, Callback *const item_cb,
                                const bool retmatchpos, list_T *const fmatchlist,
                                const int max_matches)
  FUNC_ATTR_NONNULL_ARG(2, 5, 7)
{
  int len = tv_list_len(l);
  if (len == 0) {
    return;
  }
  if (max_matches > 0 && len > max_matches) {
    len = max_matches;
  }

  fuzzyItem_T *const items = xcalloc((size_t)len, sizeof(fuzzyItem_T));
  int match_count = 0;
  uint32_t matches[FUZZY_MATCH_MAX_LEN];

  // For all the string items in items, get the fuzzy matching score
  TV_LIST_ITER(l, li, {
    if (max_matches > 0 && match_count >= max_matches) {
      break;
    }

    char *itemstr = NULL;
    bool itemstr_allocate = false;
    typval_T rettv;

    rettv.v_type = VAR_UNKNOWN;
    const typval_T *const tv = TV_LIST_ITEM_TV(li);
    if (tv->v_type == VAR_STRING) {  // list of strings
      itemstr = tv->vval.v_string;
    } else if (tv->v_type == VAR_DICT
               && (key != NULL || item_cb->type != kCallbackNone)) {
      // For a dict, either use the specified key to lookup the string or
      // use the specified callback function to get the string.
      if (key != NULL) {
        itemstr = tv_dict_get_string(tv->vval.v_dict, key, false);
      } else {
        typval_T argv[2];

        // Invoke the supplied callback (if any) to get the dict item
        tv->vval.v_dict->dv_refcount++;
        argv[0].v_type = VAR_DICT;
        argv[0].vval.v_dict = tv->vval.v_dict;
        argv[1].v_type = VAR_UNKNOWN;
        if (callback_call(item_cb, 1, argv, &rettv)) {
          if (rettv.v_type == VAR_STRING) {
            itemstr = rettv.vval.v_string;
            itemstr_allocate = true;
          }
        }
        tv_dict_unref(tv->vval.v_dict);
      }
    }

    int score;
    if (itemstr != NULL
        && fuzzy_match(itemstr, str, matchseq, &score, matches, FUZZY_MATCH_MAX_LEN)) {
      char *itemstr_copy = itemstr_allocate ? xstrdup(itemstr) : itemstr;
      list_T *match_positions = NULL;

      // Copy the list of matching positions in itemstr to a list, if
      // "retmatchpos" is set.
      if (retmatchpos) {
        match_positions = tv_list_alloc(kListLenMayKnow);
        // Fill position information
        int j = 0;
        const char *p = str;
        while (*p != NUL && j < FUZZY_MATCH_MAX_LEN) {
          if (!ascii_iswhite(utf_ptr2char(p)) || matchseq) {
            tv_list_append_number(match_positions, matches[j]);
            j++;
          }
          MB_PTR_ADV(p);
        }
      }
      items[match_count].idx = match_count;
      items[match_count].item = li;
      items[match_count].score = score;
      items[match_count].pat = str;
      items[match_count].startpos = (int)matches[0];
      items[match_count].itemstr = itemstr_copy;
      items[match_count].itemstr_allocated = itemstr_allocate;
      items[match_count].lmatchpos = match_positions;

      match_count++;
    }
    tv_clear(&rettv);
  });

  if (match_count > 0) {
    // Sort the list by the descending order of the match score
    qsort(items, (size_t)match_count, sizeof(fuzzyItem_T), fuzzy_match_item_compare);

    // For matchfuzzy(), return a list of matched strings.
    //          ['str1', 'str2', 'str3']
    // For matchfuzzypos(), return a list with three items.
    // The first item is a list of matched strings. The second item
    // is a list of lists where each list item is a list of matched
    // character positions. The third item is a list of matching scores.
    //      [['str1', 'str2', 'str3'], [[1, 3], [1, 3], [1, 3]]]
    list_T *retlist;
    if (retmatchpos) {
      const listitem_T *const li = tv_list_find(fmatchlist, 0);
      assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL);
      retlist = TV_LIST_ITEM_TV(li)->vval.v_list;
    } else {
      retlist = fmatchlist;
    }

    // Copy the matching strings to the return list
    for (int i = 0; i < match_count; i++) {
      tv_list_append_tv(retlist, TV_LIST_ITEM_TV(items[i].item));
    }

    // next copy the list of matching positions
    if (retmatchpos) {
      const listitem_T *li = tv_list_find(fmatchlist, -2);
      assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL);
      retlist = TV_LIST_ITEM_TV(li)->vval.v_list;

      for (int i = 0; i < match_count; i++) {
        assert(items[i].lmatchpos != NULL);
        tv_list_append_list(retlist, items[i].lmatchpos);
        items[i].lmatchpos = NULL;
      }

      // copy the matching scores
      li = tv_list_find(fmatchlist, -1);
      assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL);
      retlist = TV_LIST_ITEM_TV(li)->vval.v_list;
      for (int i = 0; i < match_count; i++) {
        tv_list_append_number(retlist, items[i].score);
      }
    }
  }

  for (int i = 0; i < match_count; i++) {
    if (items[i].itemstr_allocated) {
      xfree(items[i].itemstr);
    }
    assert(items[i].lmatchpos == NULL);
  }
  xfree(items);
}

/// Do fuzzy matching. Returns the list of matched strings in "rettv".
/// If "retmatchpos" is true, also returns the matching character positions.
static void do_fuzzymatch(const typval_T *const argvars, typval_T *const rettv,
                          const bool retmatchpos)
  FUNC_ATTR_NONNULL_ALL
{
  // validate and get the arguments
  if (argvars[0].v_type != VAR_LIST || argvars[0].vval.v_list == NULL) {
    semsg(_(e_listarg), retmatchpos ? "matchfuzzypos()" : "matchfuzzy()");
    return;
  }
  if (argvars[1].v_type != VAR_STRING || argvars[1].vval.v_string == NULL) {
    semsg(_(e_invarg2), tv_get_string(&argvars[1]));
    return;
  }

  Callback cb = CALLBACK_NONE;
  const char *key = NULL;
  bool matchseq = false;
  int max_matches = 0;
  if (argvars[2].v_type != VAR_UNKNOWN) {
    if (tv_check_for_nonnull_dict_arg(argvars, 2) == FAIL) {
      return;
    }

    // To search a dict, either a callback function or a key can be
    // specified.
    dict_T *const d = argvars[2].vval.v_dict;
    const dictitem_T *di;
    if ((di = tv_dict_find(d, "key", -1)) != NULL) {
      if (di->di_tv.v_type != VAR_STRING || di->di_tv.vval.v_string == NULL
          || *di->di_tv.vval.v_string == NUL) {
        semsg(_(e_invargNval), "key", tv_get_string(&di->di_tv));
        return;
      }
      key = tv_get_string(&di->di_tv);
    } else if (!tv_dict_get_callback(d, "text_cb", -1, &cb)) {
      semsg(_(e_invargval), "text_cb");
      return;
    }

    if ((di = tv_dict_find(d, "limit", -1)) != NULL) {
      if (di->di_tv.v_type != VAR_NUMBER) {
        semsg(_(e_invargval), "limit");
        return;
      }
      max_matches = (int)tv_get_number_chk(&di->di_tv, NULL);
    }

    if (tv_dict_has_key(d, "matchseq")) {
      matchseq = true;
    }
  }

  // get the fuzzy matches
  tv_list_alloc_ret(rettv, retmatchpos ? 3 : kListLenUnknown);
  if (retmatchpos) {
    // For matchfuzzypos(), a list with three items are returned. First
    // item is a list of matching strings, the second item is a list of
    // lists with matching positions within each string and the third item
    // is the list of scores of the matches.
    tv_list_append_list(rettv->vval.v_list, tv_list_alloc(kListLenUnknown));
    tv_list_append_list(rettv->vval.v_list, tv_list_alloc(kListLenUnknown));
    tv_list_append_list(rettv->vval.v_list, tv_list_alloc(kListLenUnknown));
  }

  fuzzy_match_in_list(argvars[0].vval.v_list, (char *)tv_get_string(&argvars[1]),
                      matchseq, key, &cb, retmatchpos, rettv->vval.v_list, max_matches);

  callback_free(&cb);
}

/// "matchfuzzy()" function
void f_matchfuzzy(typval_T *argvars, typval_T *rettv, EvalFuncData fptr)
{
  do_fuzzymatch(argvars, rettv, false);
}

/// "matchfuzzypos()" function
void f_matchfuzzypos(typval_T *argvars, typval_T *rettv, EvalFuncData fptr)
{
  do_fuzzymatch(argvars, rettv, true);
}

/// Same as fuzzy_match_item_compare() except for use with a string match
static int fuzzy_match_str_compare(const void *const s1, const void *const s2)
  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE
{
  const int v1 = ((fuzmatch_str_T *)s1)->score;
  const int v2 = ((fuzmatch_str_T *)s2)->score;
  const int idx1 = ((fuzmatch_str_T *)s1)->idx;
  const int idx2 = ((fuzmatch_str_T *)s2)->idx;

  if (v1 == v2) {
    return idx1 == idx2 ? 0 : idx1 > idx2 ? 1 : -1;
  } else {
    return v1 > v2 ? -1 : 1;
  }
}

/// Sort fuzzy matches by score
static void fuzzy_match_str_sort(fuzmatch_str_T *const fm, const int sz)
  FUNC_ATTR_NONNULL_ALL
{
  // Sort the list by the descending order of the match score
  qsort(fm, (size_t)sz, sizeof(fuzmatch_str_T), fuzzy_match_str_compare);
}

/// Same as fuzzy_match_item_compare() except for use with a function name
/// string match. <SNR> functions should be sorted to the end.
static int fuzzy_match_func_compare(const void *const s1, const void *const s2)
  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE
{
  const int v1 = ((fuzmatch_str_T *)s1)->score;
  const int v2 = ((fuzmatch_str_T *)s2)->score;
  const int idx1 = ((fuzmatch_str_T *)s1)->idx;
  const int idx2 = ((fuzmatch_str_T *)s2)->idx;
  const char *const str1 = ((fuzmatch_str_T *)s1)->str;
  const char *const str2 = ((fuzmatch_str_T *)s2)->str;

  if (*str1 != '<' && *str2 == '<') {
    return -1;
  }
  if (*str1 == '<' && *str2 != '<') {
    return 1;
  }
  if (v1 == v2) {
    return idx1 == idx2 ? 0 : idx1 > idx2 ? 1 : -1;
  }
  return v1 > v2 ? -1 : 1;
}

/// Sort fuzzy matches of function names by score.
/// <SNR> functions should be sorted to the end.
static void fuzzy_match_func_sort(fuzmatch_str_T *const fm, const int sz)
  FUNC_ATTR_NONNULL_ALL
{
  // Sort the list by the descending order of the match score
  qsort(fm, (size_t)sz, sizeof(fuzmatch_str_T), fuzzy_match_func_compare);
}

/// Fuzzy match "pat" in "str".
/// @returns 0 if there is no match. Otherwise, returns the match score.
int fuzzy_match_str(char *const str, const char *const pat)
  FUNC_ATTR_WARN_UNUSED_RESULT
{
  if (str == NULL || pat == NULL) {
    return 0;
  }

  int score = FUZZY_SCORE_NONE;
  uint32_t matchpos[FUZZY_MATCH_MAX_LEN];
  fuzzy_match(str, pat, true, &score, matchpos, ARRAY_SIZE(matchpos));

  return score;
}

/// Fuzzy match the position of string "pat" in string "str".
/// @returns a dynamic array of matching positions. If there is no match, returns NULL.
garray_T *fuzzy_match_str_with_pos(char *const str, const char *const pat)
{
  if (str == NULL || pat == NULL) {
    return NULL;
  }

  garray_T *match_positions = xmalloc(sizeof(garray_T));
  ga_init(match_positions, sizeof(uint32_t), 10);

  int score = FUZZY_SCORE_NONE;
  uint32_t matches[FUZZY_MATCH_MAX_LEN];
  if (!fuzzy_match(str, pat, false, &score, matches, FUZZY_MATCH_MAX_LEN)
      || score == FUZZY_SCORE_NONE) {
    ga_clear(match_positions);
    xfree(match_positions);
    return NULL;
  }

  int j = 0;
  for (const char *p = pat; *p != NUL; MB_PTR_ADV(p)) {
    if (!ascii_iswhite(utf_ptr2char(p))) {
      GA_APPEND(uint32_t, match_positions, matches[j]);
      j++;
    }
  }

  return match_positions;
}

/// This function splits the line pointed to by `*ptr` into words and performs
/// a fuzzy match for the pattern `pat` on each word. It iterates through the
/// line, moving `*ptr` to the start of each word during the process.
///
/// If a match is found:
/// - `*ptr` points to the start of the matched word.
/// - `*len` is set to the length of the matched word.
/// - `*score` contains the match score.
///
/// If no match is found, `*ptr` is updated to the end of the line.
bool fuzzy_match_str_in_line(char **ptr, char *pat, int *len, pos_T *current_pos, int *score)
{
  char *str = *ptr;
  char *strBegin = str;
  char *end = NULL;
  char *start = NULL;
  bool found = false;

  if (str == NULL || pat == NULL) {
    return found;
  }
  char *line_end = find_line_end(str);

  while (str < line_end) {
    // Skip non-word characters
    start = find_word_start(str);
    if (*start == NUL) {
      break;
    }
    end = find_word_end(start);

    // Extract the word from start to end
    char save_end = *end;
    *end = NUL;

    // Perform fuzzy match
    *score = fuzzy_match_str(start, pat);
    *end = save_end;

    if (*score != FUZZY_SCORE_NONE) {
      *len = (int)(end - start);
      found = true;
      *ptr = start;
      if (current_pos) {
        current_pos->col += (int)(end - strBegin);
      }
      break;
    }

    // Move to the end of the current word for the next iteration
    str = end;
    // Ensure we continue searching after the current word
    while (*str != NUL && !vim_iswordp(str)) {
      MB_PTR_ADV(str);
    }
  }

  if (!found) {
    *ptr = line_end;
  }

  return found;
}

/// Search for the next fuzzy match in the specified buffer.
/// This function attempts to find the next occurrence of the given pattern
/// in the buffer, starting from the current position. It handles line wrapping
/// and direction of search.
///
/// Return true if a match is found, otherwise false.
bool search_for_fuzzy_match(buf_T *buf, pos_T *pos, char *pattern, int dir, pos_T *start_pos,
                            int *len, char **ptr, int *score)
{
  pos_T current_pos = *pos;
  pos_T circly_end;
  bool found_new_match = false;
  bool looped_around = false;

  bool whole_line = ctrl_x_mode_whole_line();

  if (buf == curbuf) {
    circly_end = *start_pos;
  } else {
    circly_end.lnum = buf->b_ml.ml_line_count;
    circly_end.col = 0;
    circly_end.coladd = 0;
  }

  if (whole_line && start_pos->lnum != pos->lnum) {
    current_pos.lnum += dir;
  }

  while (true) {
    // Check if looped around and back to start position
    if (looped_around && (whole_line ? current_pos.lnum == circly_end.lnum
                                     : equalpos(current_pos, circly_end))) {
      break;
    }

    // Ensure current_pos is valid
    if (current_pos.lnum >= 1 && current_pos.lnum <= buf->b_ml.ml_line_count) {
      // Get the current line buffer
      *ptr = ml_get_buf(buf, current_pos.lnum);
      if (!whole_line) {
        *ptr += current_pos.col;
      }

      // If ptr is end of line is reached, move to next line
      // or previous line based on direction
      if (*ptr != NULL && **ptr != NUL) {
        if (!whole_line) {
          // Try to find a fuzzy match in the current line starting
          // from current position
          found_new_match = fuzzy_match_str_in_line(ptr, pattern,
                                                    len, &current_pos, score);
          if (found_new_match) {
            *pos = current_pos;
            break;
          } else if (looped_around && current_pos.lnum == circly_end.lnum) {
            break;
          }
        } else {
          if (fuzzy_match_str(*ptr, pattern) != FUZZY_SCORE_NONE) {
            found_new_match = true;
            *pos = current_pos;
            *len = ml_get_buf_len(buf, current_pos.lnum);
            break;
          }
        }
      }
    }

    // Move to the next line or previous line based on direction
    if (dir == FORWARD) {
      if (++current_pos.lnum > buf->b_ml.ml_line_count) {
        if (p_ws) {
          current_pos.lnum = 1;
          looped_around = true;
        } else {
          break;
        }
      }
    } else {
      if (--current_pos.lnum < 1) {
        if (p_ws) {
          current_pos.lnum = buf->b_ml.ml_line_count;
          looped_around = true;
        } else {
          break;
        }
      }
    }
    current_pos.col = 0;
  }

  return found_new_match;
}

/// Free an array of fuzzy string matches "fuzmatch[count]".
void fuzmatch_str_free(fuzmatch_str_T *const fuzmatch, int count)
{
  if (fuzmatch == NULL) {
    return;
  }
  for (int i = 0; i < count; i++) {
    xfree(fuzmatch[count].str);
  }
  xfree(fuzmatch);
}

/// Copy a list of fuzzy matches into a string list after sorting the matches by
/// the fuzzy score. Frees the memory allocated for "fuzmatch".
void fuzzymatches_to_strmatches(fuzmatch_str_T *const fuzmatch, char ***const matches,
                                const int count, const bool funcsort)
  FUNC_ATTR_NONNULL_ARG(2)
{
  if (count <= 0) {
    goto theend;
  }

  *matches = xmalloc((size_t)count * sizeof(char *));

  // Sort the list by the descending order of the match score
  if (funcsort) {
    fuzzy_match_func_sort(fuzmatch, count);
  } else {
    fuzzy_match_str_sort(fuzmatch, count);
  }

  for (int i = 0; i < count; i++) {
    (*matches)[i] = fuzmatch[i].str;
  }

theend:
  xfree(fuzmatch);
}

/// Fuzzy match algorithm ported from https://github.com/jhawthorn/fzy.
/// This implementation extends the original by supporting multibyte characters.

#define MATCH_MAX_LEN FUZZY_MATCH_MAX_LEN

#define SCORE_GAP_LEADING -0.005
#define SCORE_GAP_TRAILING -0.005
#define SCORE_GAP_INNER -0.01
#define SCORE_MATCH_CONSECUTIVE 1.0
#define SCORE_MATCH_SLASH 0.9
#define SCORE_MATCH_WORD 0.8
#define SCORE_MATCH_CAPITAL 0.7
#define SCORE_MATCH_DOT 0.6

static int has_match(const char *const needle, const char *const haystack)
{
  if (!needle || !haystack || !*needle) {
    return FAIL;
  }

  const char *n_ptr = needle;
  const char *h_ptr = haystack;

  while (*n_ptr) {
    const int n_char = utf_ptr2char(n_ptr);
    bool found = false;

    while (*h_ptr) {
      const int h_char = utf_ptr2char(h_ptr);
      if (n_char == h_char || mb_toupper(n_char) == h_char) {
        found = true;
        h_ptr += utfc_ptr2len(h_ptr);
        break;
      }
      h_ptr += utfc_ptr2len(h_ptr);
    }

    if (!found) {
      return FAIL;
    }

    n_ptr += utfc_ptr2len(n_ptr);
  }

  return OK;
}

struct match_struct {
  int needle_len;
  int haystack_len;
  int lower_needle[MATCH_MAX_LEN];    ///< stores codepoints
  int lower_haystack[MATCH_MAX_LEN];  ///< stores codepoints
  score_t match_bonus[MATCH_MAX_LEN];
};

#define IS_WORD_SEP(c) ((c) == '-' || (c) == '_' || (c) == ' ')
#define IS_PATH_SEP(c) ((c) == '/')
#define IS_DOT(c)      ((c) == '.')

static score_t compute_bonus_codepoint(int last_c, int c)
{
  if (ASCII_ISALNUM(c) || vim_iswordc(c)) {
    if (IS_PATH_SEP(last_c)) {
      return SCORE_MATCH_SLASH;
    }
    if (IS_WORD_SEP(last_c)) {
      return SCORE_MATCH_WORD;
    }
    if (IS_DOT(last_c)) {
      return SCORE_MATCH_DOT;
    }
    if (mb_isupper(c) && mb_islower(last_c)) {
      return SCORE_MATCH_CAPITAL;
    }
  }
  return 0;
}

static void setup_match_struct(match_struct *const match, const char *const needle,
                               const char *const haystack)
{
  int i = 0;
  const char *p = needle;
  while (*p != NUL && i < MATCH_MAX_LEN) {
    const int c = utf_ptr2char(p);
    match->lower_needle[i++] = mb_tolower(c);
    MB_PTR_ADV(p);
  }
  match->needle_len = i;

  i = 0;
  p = haystack;
  int prev_c = '/';
  while (*p != NUL && i < MATCH_MAX_LEN) {
    const int c = utf_ptr2char(p);
    match->lower_haystack[i] = mb_tolower(c);
    match->match_bonus[i] = compute_bonus_codepoint(prev_c, c);
    prev_c = c;
    MB_PTR_ADV(p);
    i++;
  }
  match->haystack_len = i;
}

static inline void match_row(const match_struct *match, int row, score_t *curr_D, score_t *curr_M,
                             const score_t *last_D, const score_t *last_M)
{
  int n = match->needle_len;
  int m = match->haystack_len;
  int i = row;

  const int *lower_needle = match->lower_needle;
  const int *lower_haystack = match->lower_haystack;
  const score_t *match_bonus = match->match_bonus;

  score_t prev_score = (score_t)SCORE_MIN;
  score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;

  // These will not be used with this value, but not all compilers see it
  score_t prev_M = (score_t)SCORE_MIN, prev_D = (score_t)SCORE_MIN;

  for (int j = 0; j < m; j++) {
    if (lower_needle[i] == lower_haystack[j]) {
      score_t score = (score_t)SCORE_MIN;
      if (!i) {
        score = (j * SCORE_GAP_LEADING) + match_bonus[j];
      } else if (j) {  // i > 0 && j > 0
        score = MAX(prev_M + match_bonus[j],
                    // consecutive match, doesn't stack with match_bonus
                    prev_D + SCORE_MATCH_CONSECUTIVE);
      }
      prev_D = last_D[j];
      prev_M = last_M[j];
      curr_D[j] = score;
      curr_M[j] = prev_score = MAX(score, prev_score + gap_score);
    } else {
      prev_D = last_D[j];
      prev_M = last_M[j];
      curr_D[j] = (score_t)SCORE_MIN;
      curr_M[j] = prev_score = prev_score + gap_score;
    }
  }
}

static score_t match_positions(const char *const needle, const char *const haystack,
                               uint32_t *const positions)
{
  if (!needle || !haystack || !*needle) {
    return (score_t)SCORE_MIN;
  }

  match_struct match;
  setup_match_struct(&match, needle, haystack);

  int n = match.needle_len;
  int m = match.haystack_len;

  if (m > MATCH_MAX_LEN || n > m) {
    // Unreasonably large candidate: return no score
    // If it is a valid match it will still be returned, it will
    // just be ranked below any reasonably sized candidates
    return (score_t)SCORE_MIN;
  } else if (n == m) {
    // Since this method can only be called with a haystack which
    // matches needle. If the lengths of the strings are equal the
    // strings themselves must also be equal (ignoring case).
    if (positions) {
      for (int i = 0; i < n; i++) {
        positions[i] = (uint32_t)i;
      }
    }
    return (score_t)SCORE_MAX;
  }

  // ensure n * MATCH_MAX_LEN * 2 won't overflow
  if ((size_t)n > (SIZE_MAX / sizeof(score_t)) / MATCH_MAX_LEN / 2) {
    return (score_t)SCORE_MIN;
  }

  // Allocate for both D and M matrices in one contiguous block
  score_t *block = (score_t *)xmalloc(sizeof(score_t) * MATCH_MAX_LEN * (size_t)n * 2);

  // D[][] Stores the best score for this position ending with a match.
  // M[][] Stores the best possible score at this position.
  score_t(*D)[MATCH_MAX_LEN] = (score_t(*)[MATCH_MAX_LEN])(block);
  score_t(*M)[MATCH_MAX_LEN] = (score_t(*)[MATCH_MAX_LEN])(block
                                                           + MATCH_MAX_LEN * (size_t)n);

  match_row(&match, 0, D[0], M[0], D[0], M[0]);
  for (int i = 1; i < n; i++) {
    match_row(&match, i, D[i], M[i], D[i - 1], M[i - 1]);
  }

  // backtrace to find the positions of optimal matching
  if (positions) {
    int match_required = 0;
    for (int i = n - 1, j = m - 1; i >= 0; i--) {
      for (; j >= 0; j--) {
        // There may be multiple paths which result in
        // the optimal weight.
        //
        // For simplicity, we will pick the first one
        // we encounter, the latest in the candidate
        // string.
        if (D[i][j] != (score_t)SCORE_MIN
            && (match_required || D[i][j] == M[i][j])) {
          // If this score was determined using
          // SCORE_MATCH_CONSECUTIVE, the
          // previous character MUST be a match
          match_required = i && j
                           && M[i][j] == D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE;
          positions[i] = (uint32_t)(j--);
          break;
        }
      }
    }
  }

  score_t result = M[n - 1][m - 1];

  xfree(block);
  return result;
}