dymokomi/luce-base
Source of release 0.44.0
0.44.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]