tobogganSe connecter

louise

The Louise language: compiler, runtime, std, tooling

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

105 lignes · 2586 octetsBrut · Historique
1/// Sorting with a C library and a Louise comparator (issue gabla108/louise#48).
2///
3/// import qsort
4///
5/// qsort.sort([3, 1, 2], fn(a, b) { a - b }) // Ok([1, 2, 3])
6///
7/// It wraps `sortkit`, whose bindings are generated from its C header. The
8/// comparator runs inside the C call (ADR 0015): it may perform `<ffi>` at
9/// most, and if it panics, the calling actor stops once the sort returns.
10
11import sortkit.{type SkVec}
12import std/ffi.{type Resource}
13import std/result
14import std/test.{assert, assert_equal}
15
16/// `xs` sorted by `compare`, which returns a negative number, zero or a
17/// positive number as `a` goes before, with or after `b`. The sort is
18/// stable. An `Error` if the C library runs out of memory.
19pub fn sort ::
20 xs: List<Int>
21 compare: fn(Int, Int) -> Int / <ffi>
22 -> Result<List<Int>, String> / <ffi>
23{
24 let v = sortkit.sk_vec_new ()
25 use _ <- result.try (push_all v xs)
26 // `sk_vec_sort` returns how many comparisons it made, and 0 when it
27 // cannot allocate its buffer: a merge of two or more elements makes one
28 // at least.
29 let comparisons = sortkit.sk_vec_sort v compare
30 let length = sortkit.sk_vec_len v
31 if length > 1 && comparisons == 0
32 {
33 Error(out_of_memory ())
34 }
35 else
36 {
37 Ok(to_list v (length - 1) [])
38 }
39}
40
41/// The version of the C library.
42pub fn version :: -> String / <ffi>
43{
44 sortkit.sk_version ()
45}
46
47/// How many of the UTF-8 bytes of `s` equal `byte`.
48pub fn count_byte :: s: String byte: Int -> Int / <ffi>
49{
50 sortkit.sk_count_byte s byte
51}
52
53fn out_of_memory :: -> String
54{
55 "sortkit: out of memory"
56}
57
58fn push_all :: v: Resource<SkVec> xs: List<Int> -> Result<(), String> / <ffi>
59{
60 match xs
61 { [] -> Ok(())
62 , [ x
63 , ..rest
64 ] -> if sortkit.sk_vec_push v x
65 {
66 push_all v rest
67 }
68 else
69 {
70 Error(out_of_memory ())
71 }
72 }
73}
74
75/// The elements at `i` and below, before `acc`. `sk_vec_get` does not
76/// check its index: `i` stays below the length.
77fn to_list :: v: Resource<SkVec> i: Int acc: List<Int> -> List<Int> / <ffi>
78{
79 if i < 0
80 {
81 acc
82 }
83 else
84 {
85 to_list v (i - 1) Cons(sortkit.sk_vec_get v i, acc)
86 }
87}
88
89@test
90fn push_all_keeps_the_order :: -> () / <ffi>
91{
92 let v = sortkit.sk_vec_new ()
93 assert (push_all v [3, 1, 2] |> result.is_ok) "pushed"
94 assert_equal (sortkit.sk_vec_len v) 3
95 assert_equal (to_list v 2 []) [3, 1, 2]
96}
97
98@test
99fn to_list_puts_the_elements_before_acc :: -> () / <ffi>
100{
101 let v = sortkit.sk_vec_new ()
102 let _ = push_all v [3, 1, 2]
103 assert_equal (to_list v 1 [0]) [3, 1, 0]
104 assert_equal (to_list v (-1) [0]) [0]
105}