packages
The Louise packages, each released on its own
Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.
Dernier runRéussi#28 · main · 3 min 34 s
0Étoiles
0Forks
3Issues
| 1 | /// Fast string search, hashing and sorting: StringZilla's SIMD kernels |
| 2 | /// (github.com/ashvardanian/StringZilla, Apache-2.0, vendored release |
| 3 | /// v4.6.3) behind a Louise API (ADR 0005). The library picks its kernels |
| 4 | /// at runtime (`capabilities` says which), so one build runs everywhere. |
| 5 | /// |
| 6 | /// import stringzilla |
| 7 | /// |
| 8 | /// stringzilla.find("hello world", "world") // Some(6), a byte offset |
| 9 | /// stringzilla.count("banana", "an") // 2 |
| 10 | /// stringzilla.sort(["b", "a", "c"]) // Ok(["a", "b", "c"]) |
| 11 | /// |
| 12 | /// Everything here performs `<ffi>`; offsets and counts are in **bytes** |
| 13 | /// (UTF-8), not characters — `string.length` counts scalar values, these |
| 14 | /// count what `string.byte_length` counts. The interpreter cannot call C: |
| 15 | /// this package's functions and tests need a native build (`louise test |
| 16 | /// --native`), as with the argon2 package. |
| 17 | /// |
| 18 | /// Not bound (see the README): edit distance and the streaming hashes |
| 19 | /// (StringZilla 4 moved them to the C++ StringZillas library, which a C |
| 20 | /// native dependency cannot build), the UTF-8 segmenters, and SHA-256. |
| 21 | |
| 22 | import bindings |
| 23 | import std/array.{type Array} |
| 24 | import std/ffi.{type Resource} |
| 25 | import std/result |
| 26 | import std/string |
| 27 | import std/test.{assert, assert_equal} |
| 28 | |
| 29 | /// The byte offset of `needle`'s first occurrence in `haystack`, or |
| 30 | /// `None`. An empty needle matches at 0. |
| 31 | pub fn find :: haystack: String needle: String -> Option<Int> / <ffi> |
| 32 | { |
| 33 | offset (bindings.szl_find haystack needle) |
| 34 | } |
| 35 | |
| 36 | /// The byte offset of `needle`'s last occurrence in `haystack`, or |
| 37 | /// `None`. An empty needle matches at `byte_length(haystack)`. |
| 38 | pub fn find_last :: haystack: String needle: String -> Option<Int> / <ffi> |
| 39 | { |
| 40 | offset (bindings.szl_rfind haystack needle) |
| 41 | } |
| 42 | |
| 43 | /// The non-overlapping occurrences of `needle` in `haystack`; an empty |
| 44 | /// needle matches at every gap: `byte_length(haystack) + 1`. |
| 45 | pub fn count :: haystack: String needle: String -> Int / <ffi> |
| 46 | { |
| 47 | bindings.szl_count haystack needle |
| 48 | } |
| 49 | |
| 50 | /// The byte offset of the first byte of `s` equal to `byte` (0 to 255), |
| 51 | /// or `None`. |
| 52 | pub fn find_byte :: s: String byte: Int -> Option<Int> / <ffi> |
| 53 | { |
| 54 | offset (bindings.szl_find_byte s byte) |
| 55 | } |
| 56 | |
| 57 | /// The byte offset of the last byte of `s` equal to `byte` (0 to 255), |
| 58 | /// or `None`. |
| 59 | pub fn find_byte_last :: s: String byte: Int -> Option<Int> / <ffi> |
| 60 | { |
| 61 | offset (bindings.szl_rfind_byte s byte) |
| 62 | } |
| 63 | |
| 64 | /// `a` against `b`, byte-wise (the order `Ord<String>` uses). |
| 65 | pub fn compare :: a: String b: String -> Order / <ffi> |
| 66 | { |
| 67 | match bindings.szl_order a b { -1 -> Lt, 0 -> Eq, _ -> Gt } |
| 68 | } |
| 69 | |
| 70 | /// The low 63 bits of StringZilla's 64-bit hash of `s` with `seed`: a |
| 71 | /// fast fingerprint, not a cryptographic hash. |
| 72 | pub fn hash :: s: String seed: Int -> Int / <ffi> |
| 73 | { |
| 74 | bindings.szl_hash s seed |
| 75 | } |
| 76 | |
| 77 | /// The low 63 bits of StringZilla's byte-sum sketch of `s`. |
| 78 | pub fn bytesum :: s: String -> Int / <ffi> |
| 79 | { |
| 80 | bindings.szl_bytesum s |
| 81 | } |
| 82 | |
| 83 | /// `xs` sorted by bytes (stable for distinct strings; equal strings are |
| 84 | /// interchangeable). An `Error` if the C library runs out of memory. |
| 85 | pub fn sort :: xs: List<String> -> Result<List<String>, String> / <ffi> |
| 86 | { |
| 87 | let s = bindings.szl_sort_new () |
| 88 | use _ <- result.try (push_all s xs) |
| 89 | if bindings.szl_sort_argsort s |
| 90 | { |
| 91 | Ok(permute s (array.from_list xs) (bindings.szl_sort_count s - 1) []) |
| 92 | } |
| 93 | else |
| 94 | { |
| 95 | Error(out_of_memory ()) |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | /// The vendored StringZilla's version: "major.minor.patch". |
| 100 | pub fn version :: -> String / <ffi> |
| 101 | { |
| 102 | bindings.szl_version () |
| 103 | } |
| 104 | |
| 105 | /// The SIMD tiers StringZilla uses on this machine, e.g. |
| 106 | /// "serial,westmere,haswell". |
| 107 | pub fn capabilities :: -> String / <ffi> |
| 108 | { |
| 109 | bindings.szl_capabilities () |
| 110 | } |
| 111 | |
| 112 | /// `Some(at)` for an offset `at` of 0 or more, `None` for -1. |
| 113 | fn offset :: at: Int -> Option<Int> |
| 114 | { |
| 115 | if at < 0 |
| 116 | { |
| 117 | None |
| 118 | } |
| 119 | else |
| 120 | { |
| 121 | Some(at) |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | fn out_of_memory :: -> String |
| 126 | { |
| 127 | "stringzilla: out of memory" |
| 128 | } |
| 129 | |
| 130 | fn push_all :: |
| 131 | s: Resource<bindings.SzlSort> |
| 132 | xs: List<String> |
| 133 | -> Result<(), String> / <ffi> |
| 134 | { |
| 135 | match xs |
| 136 | { [] -> Ok(()) |
| 137 | , [ x |
| 138 | , ..rest |
| 139 | ] -> if bindings.szl_sort_push s x |
| 140 | { |
| 141 | push_all s rest |
| 142 | } |
| 143 | else |
| 144 | { |
| 145 | Error(out_of_memory ()) |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | /// The strings of `xs` in the order `s` sorted them: the pushed index of |
| 151 | /// the i-th smallest, read back from `i = count - 1` down, onto `acc`. |
| 152 | fn permute :: |
| 153 | s: Resource<bindings.SzlSort> |
| 154 | xs: Array<String> |
| 155 | i: Int |
| 156 | acc: List<String> |
| 157 | -> List<String> / <ffi> |
| 158 | { |
| 159 | if i < 0 |
| 160 | { |
| 161 | acc |
| 162 | } |
| 163 | else |
| 164 | { |
| 165 | // The index is in range: `s` holds exactly the strings of `xs`. |
| 166 | match array.get xs (bindings.szl_sort_order s i) |
| 167 | { Some(x) -> permute s xs (i - 1) [x, ..acc] |
| 168 | , None -> panic "stringzilla: the sort returned an index out of range" |
| 169 | } |
| 170 | } |
| 171 | } |
| 172 | |
| 173 | @test |
| 174 | fn offsets_and_counts_on_fixed_strings :: -> () / <ffi> |
| 175 | { |
| 176 | assert_equal (find "hello world" "world") (Some(6)) |
| 177 | assert_equal (find "hello world" "o") (Some(4)) |
| 178 | assert_equal (find_last "hello world" "o") (Some(7)) |
| 179 | assert_equal (find "hello" "z") None |
| 180 | assert_equal (find "" "") (Some(0)) |
| 181 | assert_equal (find "abc" "") (Some(0)) |
| 182 | assert_equal (find_last "abc" "") (Some(3)) |
| 183 | assert_equal (count "banana" "an") 2 |
| 184 | assert_equal (count "aaaa" "aa") 2 |
| 185 | assert_equal (count "abc" "") 4 |
| 186 | assert_equal (count "" "") 1 |
| 187 | // "é" is two UTF-8 bytes: offsets are byte offsets. |
| 188 | assert_equal (find "héllo" "llo") (Some(3)) |
| 189 | assert_equal (string.byte_length "héllo") 6 |
| 190 | } |
| 191 | |
| 192 | @test |
| 193 | fn compare_is_byte_wise :: -> () / <ffi> |
| 194 | { |
| 195 | assert_equal (order_int (compare "abc" "abd")) (-1) |
| 196 | assert_equal (order_int (compare "abc" "abc")) 0 |
| 197 | assert_equal (order_int (compare "b" "abc")) 1 |
| 198 | assert_equal (order_int (compare "" "")) 0 |
| 199 | assert_equal (order_int (compare "abc" "ab")) 1 |
| 200 | } |
| 201 | |
| 202 | /// `Lt`, `Eq`, `Gt` as -1, 0, 1 (`Order` has no `Eq`). |
| 203 | fn order_int :: o: Order -> Int |
| 204 | { |
| 205 | match o { Lt -> -1, Eq -> 0, Gt -> 1 } |
| 206 | } |