Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / std / strings / search.lucb

#==============================================================================================
#
#   search - Substring search over `str`
#
#   DESCRIPTION:
#       Prefix, suffix, and forward or reverse substring search, all byte-exact and
#       allocation-free.
#
#==============================================================================================

## Whether `text` begins with `prefix`.
pub func starts_with(text: str, prefix: str) -> bool:
    if prefix.length > text.length:
        return false
    return (str)text.bytes[..<prefix.length] == prefix

## Whether `text` ends with `suffix`.
pub func ends_with(text: str, suffix: str) -> bool:
    if suffix.length > text.length:
        return false
    return (str)text.bytes[text.length - suffix.length..] == suffix

## The byte offset of the first exact needle, or none. Empty needles match at
## zero. No allocation or UTF-8 validation occurs; embedded NUL bytes are ordinary
## data. The search takes linear time and constant auxiliary space.
pub func find(text: str, needle: str) -> usize?:
    return search_bytes(text.bytes, needle.bytes, false)

## Search at or after a byte offset. An offset past the end returns none, including
## for an empty needle. This does not require a Unicode scalar boundary.
pub func find_from(text: str, needle: str, start: usize) -> usize?:
    if start > text.length:
        return none
    let offset = search_bytes(text.bytes[start..], needle.bytes, false) else return none
    return start + offset

## The last exact occurrence, including overlaps. Empty needles match at the end.
## Like find, this uses byte offsets, linear time, constant space and no allocation.
pub func find_last(text: str, needle: str) -> usize?:
    let offset = search_bytes(text.bytes, needle.bytes, true) else return none
    return text.length - needle.length - offset

## The byte offset of the last `byte` in `text`.
pub func last(text: str, byte: u8) -> usize?:
    var i = text.length
    while i > 0:
        i -= 1
        if text.bytes[i] == byte:
            return i
    return none

## Whether `needle` occurs anywhere in `text`.
pub func contains(text: str, needle: str) -> bool:
    return find(text, needle) != none

## Two-way matching splits the needle at a critical factorization. Match its right
## part first, then the left; the period lets repeated prefixes be skipped without
## comparing them again. Reversed indexing gives the same bound for find_last.
func search_bytes(text: const u8[], needle: const u8[], reversed: bool) -> usize?:
    if needle.length == 0:
        return 0
    if needle.length > text.length:
        return none
    let (forward_split, forward_period) = maximal_suffix(needle, reversed, false)
    let (backward_split, backward_period) = maximal_suffix(needle, reversed, true)
    var critical = forward_split
    var period = forward_period
    if backward_split > critical:
        critical = backward_split
        period = backward_period
    var periodic = critical <= needle.length - period
    var index: usize = 0
    while periodic and index < critical:
        if search_byte(needle, index, reversed) != search_byte(needle, period + index, reversed):
            periodic = false
        index += 1
    var remembered: usize = 0
    if periodic:
        remembered = needle.length - period
    else:
        let right = needle.length - critical + 1
        period = critical if critical > right else right
    var position: usize = 0
    var matched_prefix: usize = 0
    while needle.length <= text.length - position:
        var right = critical if critical > matched_prefix else matched_prefix
        while right < needle.length and search_byte(needle, right, reversed) == search_byte(text, position + right, reversed):
            right += 1
        if right < needle.length:
            position += right - critical + 1
            matched_prefix = 0
            continue
        var left = critical
        while left > matched_prefix and search_byte(needle, left - 1, reversed) == search_byte(text, position + left - 1, reversed):
            left -= 1
        if left <= matched_prefix:
            return position
        position += period
        matched_prefix = remembered
    return none

## Positions represent suffix starts rather than signed -1 sentinels. Every
## advance stays within the needle; no index arithmetic wraps at usize maximum.
func maximal_suffix(needle: const u8[], reversed: bool, opposite_order: bool) -> (usize, usize):
    var left: usize = 0
    var right: usize = 1
    var offset: usize = 0
    var period: usize = 1
    while right < needle.length and offset < needle.length - right:
        let a = search_byte(needle, right + offset, reversed)
        let b = search_byte(needle, left + offset, reversed)
        if a == b:
            if offset + 1 == period:
                right += period
                offset = 0
            else:
                offset += 1
        elif (a < b) != opposite_order:
            right += offset + 1
            offset = 0
            period = right - left
        else:
            left = right
            right = left + 1
            offset = 0
            period = 1
    return (left, period)

func search_byte(bytes: const u8[], index: usize, reversed: bool) -> u8:
    return bytes[bytes.length - index - 1] if reversed else bytes[index]