Skip to main content

Fzy

The lua implementation of the fzy string matching algorithm. This algorithm is optimized for matching stuff on the terminal, but should serve well as a baseline search algorithm within a game too.

See:

Modified from the initial code to fit this codebase. While this definitely messes with some naming which may have been better, it also keeps usage of this library consistent with other libraries.

Notes:

  • A higher score is better than a lower score
  • Scoring time is O(n*m) where n is the length of the needle and m is the length of the haystack.
  • Scoring memory is also O(n*m)
  • Should do quite well with small lists

TODO: Support UTF8

Types​

FzyConfig​

</>
interface FzyConfig {
caseSensitive: boolean
gapLeadingScore: number
gapTrailingScore: number
gapInnerScore: number
consecutiveMatchScore: number
slashMatchScore: number
wordMatchScore: number
capitalMatchScore: number
dotMatchScore: number
maxMatchLength: number
}

Configuration for Fzy. See Fzy.createConfig for details. This affects scoring and how the matching is done.

Functions​

createConfig​

</>
Fzy.createConfig(config: table) → FzyConfig

Creates a new configuration for Fzy.

isFzyConfig​

</>
Fzy.isFzyConfig(config: any) → boolean

Returns true if it is a config

hasMatch​

</>
Fzy.hasMatch(
config: FzyConfig,
needle: string,
haystack: string
) → boolean

Check if needle is a subsequence of the haystack.

Usually called before Fzy.score or Fzy.positions.

isPerfectMatch​

</>
Fzy.isPerfectMatch(
config: FzyConfig,
needle: string,--

must be a subequence of haystack, or the result is undefined.

haystack: string
) → boolean

Computes whether a needle or haystack are a perfect match or not

score​

</>
Fzy.score(
config: FzyConfig,
needle: string,--

must be a subequence of haystack, or the result is undefined.

haystack: string
) → number--

higher scores indicate better matches. See also Fzy.getMinScore and Fzy.getMaxScore.

Compute a matching score.

positions​

</>
Fzy.positions(
config: FzyConfig,
needle: string,--

must be a subequence of haystack, or the result is undefined.

haystack: string
) → (
{int},--

indices, where indices[n] is the location of the nth character of needle in haystack.

number--

the same matching score returned by score

)

Compute the locations where fzy matches a string.

Determine where each character of the needle is matched to the haystack in the optimal match.

filter​

</>
Fzy.filter(
config: FzyConfig,
needle: string,
haystacks: {string}
) → {
{
idx,
positions,
score
},
...
}

Apply Fzy.hasMatch and Fzy.positions to an array of haystacks.

Returns an array with one entry per matching line in haystacks, each entry giving the index of the line in haystacks as well as the equivalent to the return value of positions for that line.

getMinScore​

</>
Fzy.getMinScore() → number

The lowest value returned by score.

In two special cases:

the Fzy.score function will return this exact value, which can be used as a sentinel. This is the lowest possible score.

getMaxScore​

</>
Fzy.getMaxScore() → number

The score returned for exact matches. This is the highest possible score.

getMaxLength​

</>
Fzy.getMaxLength(config: FzyConfig) → number

The maximum size for which fzy will evaluate scores.

getScoreFloor​

</>
Fzy.getScoreFloor(config: FzyConfig) → number

The minimum score returned for normal matches.

For matches that don't return Fzy.getMinScore, their score will be greater than than this value.

getScoreCeiling​

</>
Fzy.getScoreCeiling(config: FzyConfig) → number

The maximum score for non-exact matches.

For matches that don't return Fzy.getMaxScore, their score will be less than this value.

Show raw api
{
    "functions": [
        {
            "name": "createConfig",
            "desc": "Creates a new configuration for Fzy.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "table"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "FzyConfig"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 79,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "isFzyConfig",
            "desc": "Returns true if it is a config",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "any"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 110,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "hasMatch",
            "desc": "Check if `needle` is a subsequence of the `haystack`.\n\nUsually called before [Fzy.score] or [Fzy.positions].",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                },
                {
                    "name": "needle",
                    "desc": "",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 134,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "isPerfectMatch",
            "desc": "Computes whether a needle or haystack are a perfect match or not",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                },
                {
                    "name": "needle",
                    "desc": "must be a subequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 243,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "score",
            "desc": "Compute a matching score.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                },
                {
                    "name": "needle",
                    "desc": "must be a subequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "higher scores indicate better matches. See also [Fzy.getMinScore] and [Fzy.getMaxScore].",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 259,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "positions",
            "desc": "Compute the locations where fzy matches a string.\n\nDetermine where each character of the `needle` is matched to the `haystack`\nin the optimal match.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                },
                {
                    "name": "needle",
                    "desc": "must be a subequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "indices, where `indices[n]` is the location of the `n`th character of `needle` in `haystack`.",
                    "lua_type": "{ int }"
                },
                {
                    "desc": "the same matching score returned by `score`",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 288,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "filter",
            "desc": "Apply [Fzy.hasMatch] and [Fzy.positions] to an array of haystacks.\n\nReturns an array with one entry per matching line in `haystacks`,\neach entry giving the index of the line in `haystacks` as well as\nthe equivalent to the return value of `positions` for that line.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                },
                {
                    "name": "needle",
                    "desc": "",
                    "lua_type": "string"
                },
                {
                    "name": "haystacks",
                    "desc": "",
                    "lua_type": "{ string }"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{{idx, positions, score}, ...}"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 337,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "getMinScore",
            "desc": "The lowest value returned by `score`.\n\nIn two special cases:\n - an empty `needle`, or\n - a `needle` or `haystack` larger than than [Fzy.getMaxLength],\n\nthe [Fzy.score] function will return this exact value, which can be used as a\nsentinel. This is the lowest possible score.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 362,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "getMaxScore",
            "desc": "The score returned for exact matches. This is the highest possible score.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 371,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "getMaxLength",
            "desc": "The maximum size for which `fzy` will evaluate scores.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 381,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "getScoreFloor",
            "desc": "The minimum score returned for normal matches.\n\nFor matches that don't return [Fzy.getMinScore], their score will be greater\nthan than this value.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 396,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        },
        {
            "name": "getScoreCeiling",
            "desc": "The maximum score for non-exact matches.\n\nFor matches that don't return [Fzy.getMaxScore], their score will be less than\nthis value.",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "FzyConfig"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 411,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        }
    ],
    "properties": [],
    "types": [
        {
            "name": "FzyConfig",
            "desc": "Configuration for Fzy. See [Fzy.createConfig] for details. This affects scoring\nand how the matching is done.",
            "fields": [
                {
                    "name": "caseSensitive",
                    "lua_type": "boolean",
                    "desc": ""
                },
                {
                    "name": "gapLeadingScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "gapTrailingScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "gapInnerScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "consecutiveMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "slashMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "wordMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "capitalMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "dotMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "maxMatchLength",
                    "lua_type": "number",
                    "desc": ""
                }
            ],
            "source": {
                "line": 72,
                "path": "src/fzy/src/Shared/Fzy.lua"
            }
        }
    ],
    "name": "Fzy",
    "desc": "The lua implementation of the fzy string matching algorithm. This algorithm\nis optimized for matching stuff on the terminal, but should serve well as a\nbaseline search algorithm within a game too.\n\nSee:\n* https://github.com/swarn/fzy-lua\n* https://github.com/jhawthorn/fzy/blob/master/ALGORITHM.md\n\nModified from the initial code to fit this codebase. While this\ndefinitely messes with some naming which may have been better, it\nalso keeps usage of this library consistent with other libraries.\n\nNotes:\n* A higher score is better than a lower score\n* Scoring time is `O(n*m)` where `n` is the length of the needle\n  and `m` is the length of the haystack.\n* Scoring memory is also `O(n*m)`\n* Should do quite well with small lists\n\nTODO: Support UTF8",
    "source": {
        "line": 25,
        "path": "src/fzy/src/Shared/Fzy.lua"
    }
}