subseq.c File Reference

Subsequence fuzzy matching implementation. More...

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

Include dependency graph for subseq.c:

Go to the source code of this file.

Macros
#define	DEFAULT_MAX_PATTERN   256
	Default maximum pattern length.

Functions
static unsigned char	ascii_tolower (unsigned char c)
	Convert ASCII character to lowercase.
static int	lower_if (int c, bool fold)
	Convert character to lowercase conditionally.
static bool	utf8_is_continuation (unsigned char c)
	Check for UTF-8 continuation byte.
static int	utf8_char_len (const char *s)
	Get length of a UTF-8 codepoint at a byte offset.
static bool	compute_case_mode (const char *pattern, const struct FuzzyOptions *opts)
	Determine if case folding should be used.
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

Subsequence fuzzy matching implementation.

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 subseq.c.

Macro Definition Documentation

DEFAULT_MAX_PATTERN

#define DEFAULT_MAX_PATTERN   256

Default maximum pattern length.

Definition at line 133 of file subseq.c.

Function Documentation

ascii_tolower()

unsigned char ascii_tolower ( unsigned char c )

inlinestatic

Convert ASCII character to lowercase.

Parameters

c	Character to convert

Return values

num	Lowercase character if ASCII A-Z, otherwise unchanged

This function only converts ASCII characters (A-Z to a-z). All other bytes (including UTF-8 continuation bytes) are left unchanged. This preserves UTF-8 sequences while allowing case-insensitive ASCII matching.

Definition at line 144 of file subseq.c.

{
  if ((c >= 'A') && (c <= 'Z'))
    return c + ('a' - 'A');
  return c;
}

Here is the caller graph for this function:

lower_if()

int lower_if ( int c, bool fold )

inlinestatic

Convert character to lowercase conditionally.

Parameters

c	Character to convert
fold	If true, convert ASCII to lowercase

Return values

num	Converted character

Only performs ASCII case folding (A-Z to a-z). All other bytes are left unchanged, preserving UTF-8 sequences.

Definition at line 160 of file subseq.c.

{
  return fold ? ascii_tolower((unsigned char) c) : c;
}

Here is the call graph for this function:

Here is the caller graph for this function:

utf8_is_continuation()

bool utf8_is_continuation ( unsigned char c )

inlinestatic

Check for UTF-8 continuation byte.

Parameters

c	Byte to check

Return values

true	Byte is in range 0x80-0xBF
false	Byte is not a continuation byte

Definition at line 171 of file subseq.c.

{
  return (c & 0xC0) == 0x80;
}

Here is the caller graph for this function:

utf8_char_len()

int utf8_char_len ( const char * s )

static

Get length of a UTF-8 codepoint at a byte offset.

Parameters

s	String position

Return values

num	Number of bytes in this codepoint (1-4)

Returns 1 for ASCII and malformed sequences.

Definition at line 183 of file subseq.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

compute_case_mode()

bool compute_case_mode ( const char * pattern, const struct FuzzyOptions * opts )

static

Determine if case folding should be used.

Parameters

pattern	Pattern string
opts	Fuzzy matching options

Return values

true	Use case-insensitive matching (ASCII only)
false	Use case-sensitive matching

Smart case only examines ASCII characters (A-Z). Non-ASCII bytes are ignored for smart case detection.

Definition at line 227 of file subseq.c.

{
  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
}

Here is the caller graph for this function:

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] = { 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;
}

Here is the call graph for this function:

Here is the caller graph for this function: