subseq.c

Go to the documentation of this file.

 
#include "config.h"
#include <stdbool.h>
#include <string.h>
#include "lib.h"
#include "fuzzy.h"

#define DEFAULT_MAX_PATTERN 256

static inline unsigned char ascii_tolower(unsigned char c)
{
  if ((c >= 'A') && (c <= 'Z'))
    return c + ('a' - 'A');
  return c;
}

static inline int lower_if(int c, bool fold)
{
  return fold ? ascii_tolower((unsigned char) c) : c;
}

static inline bool utf8_is_continuation(unsigned char c)
{
  return (c & 0xC0) == 0x80;
}

static int utf8_char_len(const char *s)
{
  const unsigned char c0 = (unsigned char) s[0];
 
  if (c0 < 0x80)
    return 1;
 
  if ((c0 >= 0xC2) && (c0 <= 0xDF))
  {
    if (s[1] && utf8_is_continuation((unsigned char) s[1]))
      return 2;
    return 1;
  }
 
  if ((c0 >= 0xE0) && (c0 <= 0xEF))
  {
    if (s[1] && s[2] && utf8_is_continuation((unsigned char) s[1]) &&
        utf8_is_continuation((unsigned char) s[2]))
      return 3;
    return 1;
  }
 
  if ((c0 >= 0xF0) && (c0 <= 0xF4))
  {
    if (s[1] && s[2] && s[3] && utf8_is_continuation((unsigned char) s[1]) &&
        utf8_is_continuation((unsigned char) s[2]) &&
        utf8_is_continuation((unsigned char) s[3]))
      return 4;
    return 1;
  }
 
  return 1;
}

static bool compute_case_mode(const char *pattern, const struct FuzzyOptions *opts)
{
  if (!opts)
    return true; // default case-insensitive
 
  if (opts->case_sensitive)
    return false;
 
  if (opts->smart_case)
  {
    // Check if pattern contains any ASCII uppercase (A-Z)
    for (const char *p = pattern; *p; p++)
    {
      unsigned char c = (unsigned char) *p;
      if ((c >= 'A') && (c <= 'Z'))
        return false; // found uppercase, use case-sensitive
    }
  }
 
  return true; // fold case
}

int fuzzy_subseq_match(const char *pattern, const char *candidate,
                       const struct FuzzyOptions *opts, struct FuzzyResult *out)
{
  if (!pattern || !candidate)
    return -1;
 
  size_t plen = strlen(pattern);
  if (plen == 0)
    return -1;
 
  int max_pattern = (opts && opts->max_pattern) ? opts->max_pattern : DEFAULT_MAX_PATTERN;
  if ((max_pattern <= 0) || (max_pattern > DEFAULT_MAX_PATTERN))
    max_pattern = DEFAULT_MAX_PATTERN;
 
  if (plen > (size_t) max_pattern)
    return -1;
 
  bool fold = compute_case_mode(pattern, opts);
 
  int matchpos[DEFAULT_MAX_PATTERN] = { 0 };
 
  int pi = 0;
  int ci = 0;
  int score = 0;
 
  int first = -1;
  int last = -1;
 
  // Forward subsequence scan
  while (candidate[ci] && pi < (int) plen)
  {
    const unsigned char pbyte = (unsigned char) pattern[pi];
    if (pbyte < 0x80)
    {
      int pc = lower_if(pattern[pi], fold);
      int cc = lower_if(candidate[ci], fold);
 
      if (pc == cc)
      {
        matchpos[pi] = ci;
 
        if (first < 0)
          first = ci;
 
        last = ci;
        pi++;
      }
 
      ci++;
      continue;
    }
 
    // Non-ASCII pattern bytes must match as a whole UTF-8 codepoint.
    const int pchar_len = utf8_char_len(pattern + pi);
    const int premaining = (int) plen - pi;
    if ((pchar_len <= 0) || (pchar_len > premaining))
      return -1;
    bool matched = false;
 
    while (candidate[ci])
    {
      const unsigned char cbyte = (unsigned char) candidate[ci];
      if (utf8_is_continuation(cbyte))
      {
        ci++;
        continue;
      }
 
      const int cchar_len = utf8_char_len(candidate + ci);
      if ((pchar_len == cchar_len) && (memcmp(pattern + pi, candidate + ci, pchar_len) == 0))
      {
        for (int k = 0; k < pchar_len; k++)
        {
          const int match_idx = pi + k;
          if (match_idx >= DEFAULT_MAX_PATTERN)
            return -1;
          matchpos[match_idx] = ci + k;
        }
 
        if (first < 0)
          first = ci;
 
        last = ci + pchar_len - 1;
        pi += pchar_len;
        ci += cchar_len;
        matched = true;
        break;
      }
 
      ci += cchar_len;
    }
 
    if (!matched)
      break;
  }
 
  if (pi != (int) plen)
    return -1; // not a subsequence
 
  // Scoring
 
  // Base score
  score += plen * 10;
 
  // Consecutive & gap penalties
  for (int i = 1; i < pi; i++)
  {
    int gap = matchpos[i] - matchpos[i - 1] - 1;
 
    if (gap == 0)
      score += 15; // compact match bonus
    else
      score -= gap * 2;
  }
 
  // Span penalty
  int span = last - first + 1;
  score -= span;
 
  // Prefix bonus
  if (first == 0 && opts && opts->prefer_prefix)
    score += 40;
 
  // Boundary bonus (ASCII-only separators and CamelCase)
  for (int i = 0; i < pi; i++)
  {
    int pos = matchpos[i];
 
    if (pos == 0)
      score += 30; // start of string
    else
    {
      unsigned char prev = (unsigned char) candidate[pos - 1];
      unsigned char curr = (unsigned char) candidate[pos];
 
      // ASCII separator boundaries
      if ((prev == '/') || (prev == '.') || (prev == '-') || (prev == '_'))
        score += 15;
      // ASCII CamelCase boundary (lowercase followed by uppercase)
      else if (((prev >= 'a') && (prev <= 'z')) && ((curr >= 'A') && (curr <= 'Z')))
        score += 10;
    }
  }
 
  // Mild length penalty
  score -= (int) strlen(candidate) / 4;
 
  // Ensure valid matches always return non-negative score
  if (score < 0)
    score = 0;
 
  if (out)
  {
    out->score = score;
    out->span = span;
    out->start = first;
    out->end = last;
  }
 
  return score;
}