tobogganSe connecter

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.

206 lignes · 5833 octetsBrut · Historique
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
22import bindings
23import std/array.{type Array}
24import std/ffi.{type Resource}
25import std/result
26import std/string
27import 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.
31pub 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)`.
38pub 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`.
45pub 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`.
52pub 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`.
59pub 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).
65pub 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.
72pub 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`.
78pub 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.
85pub 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".
100pub 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".
107pub 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.
113fn offset :: at: Int -> Option<Int>
114{
115 if at < 0
116 {
117 None
118 }
119 else
120 {
121 Some(at)
122 }
123}
124
125fn out_of_memory :: -> String
126{
127 "stringzilla: out of memory"
128}
129
130fn 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`.
152fn 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
174fn 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
193fn 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`).
203fn order_int :: o: Order -> Int
204{
205 match o { Lt -> -1, Eq -> 0, Gt -> 1 }
206}