fuzzy.h File Reference

Fuzzy matching library - private definitions. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
int	fuzzy_subseq_match (const char *pattern, const char *candidate, const struct FuzzyOptions *opts, struct FuzzyResult *out)
	Perform subsequence fuzzy matching (UTF-8 aware, ASCII case-folding)

Detailed Description

Fuzzy matching library - private definitions.

Authors

• Richard Russon

Copyright

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file fuzzy.h.

Function Documentation

fuzzy_subseq_match()

int fuzzy_subseq_match	(	const char *	pattern,
		const char *	candidate,
		const struct FuzzyOptions *	opts,
		struct FuzzyResult *	out )

Perform subsequence fuzzy matching (UTF-8 aware, ASCII case-folding)

Parameters

pattern	Pattern to match (UTF-8 byte sequence)
candidate	Candidate string to match against (UTF-8 byte sequence)
opts	Fuzzy matching options
out	Output result structure

Return values

>=0	Match score
-1	Error or no match

Performs byte-wise subsequence matching with ASCII-only case folding. UTF-8 multi-byte sequences are preserved but matched as raw bytes. Only ASCII A-Z characters are case-folded to a-z.

Definition at line 262 of file subseq.c.

{
  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];
 
  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++)
          matchpos[pi + k] = 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;
}

Here is the call graph for this function:

Here is the caller graph for this function: