eurydice_glue.h (21008B)
1 #pragma once 2 3 #include <inttypes.h> 4 #include <stdbool.h> 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <string.h> 8 9 #ifdef _MSC_VER 10 // For __popcnt 11 #include <intrin.h> 12 #endif 13 14 #include "krml/internal/target.h" 15 #include "krml/lowstar_endianness.h" 16 17 // C++ HELPERS 18 19 #if defined(__cplusplus) 20 21 #ifndef KRML_HOST_EPRINTF 22 #define KRML_HOST_EPRINTF(...) fprintf(stderr, __VA_ARGS__) 23 #endif 24 25 #include <utility> 26 27 #ifndef __cpp_lib_type_identity 28 template <class T> 29 struct type_identity { 30 using type = T 31 }; 32 33 template <class T> 34 using type_identity_t = typename type_identity<T>::type; 35 #else 36 using std::type_identity_t; 37 #endif 38 39 #define KRML_UNION_CONSTRUCTOR(T) \ 40 template <typename V> \ 41 constexpr T(int t, V U::*m, type_identity_t<V> v) : tag(t) \ 42 { \ 43 val.*m = std::move(v); \ 44 } \ 45 T() = default; 46 47 #endif 48 49 // GENERAL-PURPOSE STUFF 50 51 #define LowStar_Ignore_ignore(e, t, _ret_t) ((void)e) 52 53 #define EURYDICE_ASSERT(test, msg) \ 54 do { \ 55 if (!(test)) { \ 56 fprintf(stderr, "assertion \"%s\" failed: file \"%s\", line %d\n", msg, \ 57 __FILE__, __LINE__); \ 58 exit(255); \ 59 } \ 60 } while (0) 61 62 // SLICES, ARRAYS, ETC. 63 64 // We represent a slice as a pair of an (untyped) pointer, along with the length 65 // of the slice, i.e. the number of elements in the slice (this is NOT the 66 // number of bytes). This design choice has two important consequences. 67 // - if you need to use `ptr`, you MUST cast it to a proper type *before* 68 // performing pointer arithmetic on it (remember that C desugars pointer 69 // arithmetic based on the type of the address) 70 // - if you need to use `len` for a C style function (e.g. memcpy, memcmp), you 71 // need to multiply it by sizeof t, where t is the type of the elements. 72 // 73 // Empty slices have `len == 0` and `ptr` always needs to be a valid pointer 74 // that is not NULL (otherwise the construction in EURYDICE_SLICE computes `NULL 75 // + start`). 76 typedef struct { 77 void *ptr; 78 size_t len; 79 } Eurydice_slice; 80 81 #if defined(__cplusplus) 82 #define KRML_CLITERAL(type) type 83 #else 84 #define KRML_CLITERAL(type) (type) 85 #endif 86 87 #if defined(__cplusplus) && defined(__cpp_designated_initializers) || \ 88 !(defined(__cplusplus)) 89 #define EURYDICE_CFIELD(X) X 90 #else 91 #define EURYDICE_CFIELD(X) 92 #endif 93 94 // Helper macro to create a slice out of a pointer x, a start index in x 95 // (included), and an end index in x (excluded). The argument x must be suitably 96 // cast to something that can decay (see remark above about how pointer 97 // arithmetic works in C), meaning either pointer or array type. 98 #define EURYDICE_SLICE(x, start, end) \ 99 (KRML_CLITERAL(Eurydice_slice){ (void *)(x + start), end - start }) 100 101 // Slice length 102 #define EURYDICE_SLICE_LEN(s, _) (s).len 103 #define Eurydice_slice_len(s, _) (s).len 104 105 // This macro is a pain because in case the dereferenced element type is an 106 // array, you cannot simply write `t x` as it would yield `int[4] x` instead, 107 // which is NOT correct C syntax, so we add a dedicated phase in Eurydice that 108 // adds an extra argument to this macro at the last minute so that we have the 109 // correct type of *pointers* to elements. 110 #define Eurydice_slice_index(s, i, t, t_ptr_t) (((t_ptr_t)s.ptr)[i]) 111 112 // The following functions get sub slices from a slice. 113 114 #define Eurydice_slice_subslice(s, r, t, _0, _1) \ 115 EURYDICE_SLICE((t *)s.ptr, r.start, r.end) 116 117 // Variant for when the start and end indices are statically known (i.e., the 118 // range argument `r` is a literal). 119 #define Eurydice_slice_subslice2(s, start, end, t) \ 120 EURYDICE_SLICE((t *)s.ptr, (start), (end)) 121 122 #define Eurydice_slice_subslice_to(s, subslice_end_pos, t, _0, _1) \ 123 EURYDICE_SLICE((t *)s.ptr, 0, subslice_end_pos) 124 125 #define Eurydice_slice_subslice_from(s, subslice_start_pos, t, _0, _1) \ 126 EURYDICE_SLICE((t *)s.ptr, subslice_start_pos, s.len) 127 128 #define Eurydice_array_to_slice(end, x, t) \ 129 EURYDICE_SLICE(x, 0, \ 130 end) /* x is already at an array type, no need for cast */ 131 #define Eurydice_array_to_subslice(_arraylen, x, r, t, _0, _1) \ 132 EURYDICE_SLICE((t *)x, r.start, r.end) 133 134 // Same as above, variant for when start and end are statically known 135 #define Eurydice_array_to_subslice2(x, start, end, t) \ 136 EURYDICE_SLICE((t *)x, (start), (end)) 137 138 // Same as above, variant for when start and end are statically known 139 #define Eurydice_array_to_subslice3(x, start, end, t_ptr) \ 140 EURYDICE_SLICE((t_ptr)x, (start), (end)) 141 142 #define Eurydice_array_repeat(dst, len, init, t) \ 143 ERROR "should've been desugared" 144 145 // The following functions convert an array into a slice. 146 147 #define Eurydice_array_to_subslice_to(_size, x, r, t, _range_t, _0) \ 148 EURYDICE_SLICE((t *)x, 0, r) 149 #define Eurydice_array_to_subslice_from(size, x, r, t, _range_t, _0) \ 150 EURYDICE_SLICE((t *)x, r, size) 151 152 // Copy a slice with memcopy 153 #define Eurydice_slice_copy(dst, src, t) \ 154 memcpy(dst.ptr, src.ptr, dst.len * sizeof(t)) 155 156 #define core_array___Array_T__N___as_slice(len_, ptr_, t, _ret_t) \ 157 KRML_CLITERAL(Eurydice_slice) { ptr_, len_ } 158 159 #define core_array__core__clone__Clone_for__Array_T__N___clone( \ 160 len, src, dst, elem_type, _ret_t) \ 161 (memcpy(dst, src, len * sizeof(elem_type))) 162 #define TryFromSliceError uint8_t 163 #define core_array_TryFromSliceError uint8_t 164 165 #define Eurydice_array_eq(sz, a1, a2, t) (memcmp(a1, a2, sz * sizeof(t)) == 0) 166 167 // core::cmp::PartialEq<&0 (@Slice<U>)> for @Array<T, N> 168 #define Eurydice_array_eq_slice(sz, a1, s2, t, _) \ 169 (memcmp(a1, (s2)->ptr, sz * sizeof(t)) == 0) 170 171 #define core_array_equality___core__cmp__PartialEq__Array_U__N___for__Array_T__N____eq( \ 172 sz, a1, a2, t, _, _ret_t) \ 173 Eurydice_array_eq(sz, a1, a2, t, _) 174 #define core_array_equality___core__cmp__PartialEq__0___Slice_U____for__Array_T__N___3__eq( \ 175 sz, a1, a2, t, _, _ret_t) \ 176 Eurydice_array_eq(sz, a1, ((a2)->ptr), t, _) 177 178 #define Eurydice_slice_split_at(slice, mid, element_type, ret_t) \ 179 KRML_CLITERAL(ret_t) \ 180 { \ 181 EURYDICE_CFIELD(.fst =) \ 182 EURYDICE_SLICE((element_type *)(slice).ptr, 0, mid), \ 183 EURYDICE_CFIELD(.snd =) \ 184 EURYDICE_SLICE((element_type *)(slice).ptr, mid, (slice).len) \ 185 } 186 187 #define Eurydice_slice_split_at_mut(slice, mid, element_type, ret_t) \ 188 KRML_CLITERAL(ret_t) \ 189 { \ 190 EURYDICE_CFIELD(.fst =) \ 191 KRML_CLITERAL(Eurydice_slice){ EURYDICE_CFIELD(.ptr =)(slice.ptr), \ 192 EURYDICE_CFIELD(.len =) mid }, \ 193 EURYDICE_CFIELD(.snd =) KRML_CLITERAL(Eurydice_slice) \ 194 { \ 195 EURYDICE_CFIELD(.ptr =) \ 196 ((char *)slice.ptr + mid * sizeof(element_type)), \ 197 EURYDICE_CFIELD(.len =)(slice.len - mid) \ 198 } \ 199 } 200 201 // Conversion of slice to an array, rewritten (by Eurydice) to name the 202 // destination array, since arrays are not values in C. 203 // N.B.: see note in karamel/lib/Inlining.ml if you change this. 204 #define Eurydice_slice_to_array2(dst, src, _0, t_arr, _1) \ 205 Eurydice_slice_to_array3(&(dst)->tag, (char *)&(dst)->val.case_Ok, src, \ 206 sizeof(t_arr)) 207 208 static inline void 209 Eurydice_slice_to_array3(uint8_t *dst_tag, char *dst_ok, 210 Eurydice_slice src, size_t sz) 211 { 212 *dst_tag = 0; 213 memcpy(dst_ok, src.ptr, sz); 214 } 215 216 // SUPPORT FOR DSTs (Dynamically-Sized Types) 217 218 // A DST is a fat pointer that keeps tracks of the size of it flexible array 219 // member. Slices are a specific case of DSTs, where [T; N] implements 220 // Unsize<[T]>, meaning an array of statically known size can be converted to a 221 // fat pointer, i.e. a slice. 222 // 223 // Unlike slices, DSTs have a built-in definition that gets monomorphized, of 224 // the form: 225 // 226 // typedef struct { 227 // T *ptr; 228 // size_t len; // number of elements 229 // } Eurydice_dst; 230 // 231 // Furthermore, T = T0<[U0]> where `struct T0<U: ?Sized>`, where the `U` is the 232 // last field. This means that there are two monomorphizations of T0 in the 233 // program. One is `T0<[V; N]>` 234 // -- this is directly converted to a Eurydice_dst via suitable codegen (no 235 // macro). The other is `T = T0<[U]>`, where `[U]` gets emitted to 236 // `Eurydice_derefed_slice`, a type that only appears in that precise situation 237 // and is thus defined to give rise to a flexible array member. 238 239 typedef char Eurydice_derefed_slice[]; 240 241 #define Eurydice_slice_of_dst(fam_ptr, len_, t, _) \ 242 ((Eurydice_slice){ .ptr = (void *)(fam_ptr), .len = len_ }) 243 244 #define Eurydice_slice_of_boxed_array(ptr_, len_, t, _) \ 245 ((Eurydice_slice){ .ptr = (void *)(ptr_), .len = len_ }) 246 247 // CORE STUFF (conversions, endianness, ...) 248 249 // We slap extern "C" on declarations that intend to implement a prototype 250 // generated by Eurydice, because Eurydice prototypes are always emitted within 251 // an extern "C" block, UNLESS you use -fcxx17-compat, in which case, you must 252 // pass -DKRML_CXX17_COMPAT="" to your C++ compiler. 253 #if defined(__cplusplus) && !defined(KRML_CXX17_COMPAT) 254 extern "C" { 255 #endif 256 257 static inline void 258 core_num__u32__to_be_bytes(uint32_t src, uint8_t dst[4]) 259 { 260 // TODO: why not store32_be? 261 uint32_t x = htobe32(src); 262 memcpy(dst, &x, 4); 263 } 264 265 static inline void 266 core_num__u32__to_le_bytes(uint32_t src, uint8_t dst[4]) 267 { 268 store32_le(dst, src); 269 } 270 271 static inline uint32_t 272 core_num__u32__from_le_bytes(uint8_t buf[4]) 273 { 274 return load32_le(buf); 275 } 276 277 static inline void 278 core_num__u64__to_le_bytes(uint64_t v, uint8_t buf[8]) 279 { 280 store64_le(buf, v); 281 } 282 283 static inline uint64_t 284 core_num__u64__from_le_bytes(uint8_t buf[8]) 285 { 286 return load64_le(buf); 287 } 288 289 static inline int64_t 290 core_convert_num___core__convert__From_i32__for_i64___from(int32_t x) 291 { 292 return x; 293 } 294 295 static inline uint64_t 296 core_convert_num___core__convert__From_u8__for_u64___from(uint8_t x) 297 { 298 return x; 299 } 300 301 static inline uint64_t 302 core_convert_num___core__convert__From_u16__for_u64___from(uint16_t x) 303 { 304 return x; 305 } 306 307 static inline size_t 308 core_convert_num___core__convert__From_u16__for_usize___from(uint16_t x) 309 { 310 return x; 311 } 312 313 static inline uint32_t 314 core_num__u8__count_ones(uint8_t x0) 315 { 316 #ifdef _MSC_VER 317 return __popcnt(x0); 318 #else 319 return __builtin_popcount(x0); 320 #endif 321 } 322 323 static inline uint32_t 324 core_num__i32__count_ones(int32_t x0) 325 { 326 #ifdef _MSC_VER 327 return __popcnt(x0); 328 #else 329 return __builtin_popcount(x0); 330 #endif 331 } 332 333 static inline size_t 334 core_cmp_impls___core__cmp__Ord_for_usize___min(size_t a, 335 size_t b) 336 { 337 if (a <= b) 338 return a; 339 else 340 return b; 341 } 342 343 // unsigned overflow wraparound semantics in C 344 static inline uint16_t 345 core_num__u16__wrapping_add(uint16_t x, uint16_t y) 346 { 347 return x + y; 348 } 349 static inline uint8_t 350 core_num__u8__wrapping_sub(uint8_t x, uint8_t y) 351 { 352 return x - y; 353 } 354 static inline uint64_t 355 core_num__u64__rotate_left(uint64_t x0, uint32_t x1) 356 { 357 return (x0 << x1 | x0 >> (64 - x1)); 358 } 359 360 static inline void 361 core_ops_arith__i32__add_assign(int32_t *x0, int32_t *x1) 362 { 363 *x0 = *x0 + *x1; 364 } 365 366 static inline uint8_t 367 Eurydice_bitand_pv_u8(uint8_t *p, uint8_t v) 368 { 369 return (*p) & v; 370 } 371 static inline uint8_t 372 Eurydice_shr_pv_u8(uint8_t *p, int32_t v) 373 { 374 return (*p) >> v; 375 } 376 static inline uint32_t 377 Eurydice_min_u32(uint32_t x, uint32_t y) 378 { 379 return x < y ? x : y; 380 } 381 382 static inline uint8_t 383 core_ops_bit___core__ops__bit__BitAnd_u8__u8__for___a__u8___46__bitand( 384 uint8_t *x0, uint8_t x1) 385 { 386 return Eurydice_bitand_pv_u8(x0, x1); 387 } 388 389 static inline uint8_t 390 core_ops_bit___core__ops__bit__Shr_i32__u8__for___a__u8___792__shr(uint8_t *x0, 391 int32_t x1) 392 { 393 return Eurydice_shr_pv_u8(x0, x1); 394 } 395 396 #define core_num_nonzero_private_NonZeroUsizeInner size_t 397 static inline core_num_nonzero_private_NonZeroUsizeInner 398 core_num_nonzero_private___core__clone__Clone_for_core__num__nonzero__private__NonZeroUsizeInner__26__clone( 399 core_num_nonzero_private_NonZeroUsizeInner *x0) 400 { 401 return *x0; 402 } 403 404 #if defined(__cplusplus) && !defined(KRML_CXX17_COMPAT) 405 } 406 #endif 407 408 // ITERATORS 409 410 #define Eurydice_range_iter_next(iter_ptr, t, ret_t) \ 411 (((iter_ptr)->start >= (iter_ptr)->end) \ 412 ? (KRML_CLITERAL(ret_t){ EURYDICE_CFIELD(.tag =) 0, \ 413 EURYDICE_CFIELD(.f0 =) 0 }) \ 414 : (KRML_CLITERAL(ret_t){ EURYDICE_CFIELD(.tag =) 1, \ 415 EURYDICE_CFIELD(.f0 =)(iter_ptr)->start++ })) 416 417 #define core_iter_range___core__iter__traits__iterator__Iterator_A__for_core__ops__range__Range_A__TraitClause_0___6__next \ 418 Eurydice_range_iter_next 419 420 // See note in karamel/lib/Inlining.ml if you change this 421 #define Eurydice_into_iter(x, t, _ret_t, _) (x) 422 #define core_iter_traits_collect___core__iter__traits__collect__IntoIterator_Clause1_Item__I__for_I__1__into_iter \ 423 Eurydice_into_iter 424 425 typedef struct { 426 Eurydice_slice slice; 427 size_t chunk_size; 428 } Eurydice_chunks; 429 430 // Can't use macros Eurydice_slice_subslice_{to,from} because they require a 431 // type, and this static inline function cannot receive a type as an argument. 432 // Instead, we receive the element size and use it to peform manual offset 433 // computations rather than going through the macros. 434 static inline Eurydice_slice 435 chunk_next(Eurydice_chunks *chunks, 436 size_t element_size) 437 { 438 size_t chunk_size = chunks->slice.len >= chunks->chunk_size 439 ? chunks->chunk_size 440 : chunks->slice.len; 441 Eurydice_slice curr_chunk; 442 curr_chunk.ptr = chunks->slice.ptr; 443 curr_chunk.len = chunk_size; 444 chunks->slice.ptr = (char *)(chunks->slice.ptr) + chunk_size * element_size; 445 chunks->slice.len = chunks->slice.len - chunk_size; 446 return curr_chunk; 447 } 448 449 // using it anyway?? 450 #define Eurydice_slice_subslice3(s, start, end, t_ptr) \ 451 EURYDICE_SLICE((t_ptr)s.ptr, (start), (end)) 452 453 #define core_slice___Slice_T___chunks(slice_, sz_, t, _ret_t) \ 454 ((Eurydice_chunks){ .slice = slice_, .chunk_size = sz_ }) 455 #define core_slice___Slice_T___chunks_exact(slice_, sz_, t, _ret_t) \ 456 ((Eurydice_chunks){ \ 457 .slice = { .ptr = slice_.ptr, .len = slice_.len - (slice_.len % sz_) }, \ 458 .chunk_size = sz_ }) 459 #define core_slice_iter_Chunks Eurydice_chunks 460 #define core_slice_iter_ChunksExact Eurydice_chunks 461 #define Eurydice_chunks_next(iter, t, ret_t) \ 462 (((iter)->slice.len == 0) ? ((ret_t){ .tag = core_option_None }) \ 463 : ((ret_t){ .tag = core_option_Some, \ 464 .f0 = chunk_next(iter, sizeof(t)) })) 465 #define core_slice_iter___core__iter__traits__iterator__Iterator_for_core__slice__iter__Chunks__a__T___70__next \ 466 Eurydice_chunks_next 467 // This name changed on 20240627 468 #define core_slice_iter___core__iter__traits__iterator__Iterator_for_core__slice__iter__Chunks__a__T___71__next \ 469 Eurydice_chunks_next 470 #define core_slice_iter__core__slice__iter__ChunksExact__a__T__89__next( \ 471 iter, t, _ret_t) \ 472 core_slice_iter__core__slice__iter__Chunks__a__T__70__next(iter, t) 473 474 typedef struct { 475 Eurydice_slice s; 476 size_t index; 477 } Eurydice_slice_iterator; 478 479 #define core_slice___Slice_T___iter(x, t, _ret_t) \ 480 ((Eurydice_slice_iterator){ .s = x, .index = 0 }) 481 #define core_slice_iter_Iter Eurydice_slice_iterator 482 #define core_slice_iter__core__slice__iter__Iter__a__T__181__next(iter, t, \ 483 ret_t) \ 484 (((iter)->index == (iter)->s.len) \ 485 ? (KRML_CLITERAL(ret_t){ .tag = core_option_None }) \ 486 : (KRML_CLITERAL(ret_t){ \ 487 .tag = core_option_Some, \ 488 .f0 = ((iter)->index++, \ 489 &((t *)((iter)->s.ptr))[(iter)->index - 1]) })) 490 #define core_option__core__option__Option_T__TraitClause_0___is_some(X, _0, \ 491 _1) \ 492 ((X)->tag == 1) 493 // STRINGS 494 495 typedef const char *Prims_string; 496 497 // MISC (UNTESTED) 498 499 typedef void *core_fmt_Formatter; 500 typedef void *core_fmt_Arguments; 501 typedef void *core_fmt_rt_Argument; 502 #define core_fmt_rt__core__fmt__rt__Argument__a__1__new_display(x1, x2, x3, \ 503 x4) \ 504 NULL 505 506 // BOXES 507 508 // Crimes. 509 static inline char * 510 malloc_and_init(size_t sz, char *init) 511 { 512 char *ptr = (char *)malloc(sz); 513 memcpy(ptr, init, sz); 514 return ptr; 515 } 516 517 #define Eurydice_box_new(init, t, t_dst) \ 518 ((t_dst)(malloc_and_init(sizeof(t), (char *)(&init)))) 519 520 #define Eurydice_box_new_array(len, ptr, t, t_dst) \ 521 ((t_dst)(malloc_and_init(len * sizeof(t), (char *)(ptr)))) 522 523 // VECTORS (ANCIENT, POSSIBLY UNTESTED) 524 525 /* For now these are passed by value -- three words. We could conceivably change 526 * the representation to heap-allocate this struct and only pass around the 527 * pointer (one word). */ 528 typedef struct { 529 void *ptr; 530 size_t len; /* the number of elements */ 531 size_t alloc_size; /* the size of the allocation, in number of BYTES */ 532 } Eurydice_vec_s, *Eurydice_vec; 533 534 /* Here, we set everything to zero rather than use a non-standard GCC 535 * statement-expression -- this suitably initializes ptr to NULL and len and 536 * size to 0. */ 537 #define EURYDICE_VEC_NEW(_) calloc(1, sizeof(Eurydice_vec_s)) 538 #define EURYDICE_VEC_PUSH(v, x, t) \ 539 do { \ 540 /* Grow the vector if capacity has been reached. */ \ 541 if (v->len == v->alloc_size / sizeof(t)) { \ 542 /* Assuming that this does not exceed SIZE_MAX, because code proven \ 543 * correct by Aeneas. Would this even happen in practice? */ \ 544 size_t new_size; \ 545 if (v->alloc_size == 0) \ 546 new_size = 8 * sizeof(t); \ 547 else if (v->alloc_size <= SIZE_MAX / 2) \ 548 /* TODO: discuss growth policy */ \ 549 new_size = 2 * v->alloc_size; \ 550 else \ 551 new_size = (SIZE_MAX / sizeof(t)) * sizeof(t); \ 552 v->ptr = realloc(v->ptr, new_size); \ 553 v->alloc_size = new_size; \ 554 } \ 555 ((t *)v->ptr)[v->len] = x; \ 556 v->len++; \ 557 } while (0) 558 559 #define EURYDICE_VEC_DROP(v, t) \ 560 do { \ 561 free(v->ptr); \ 562 free(v); \ 563 } while (0) 564 565 #define EURYDICE_VEC_INDEX(v, i, t) &((t *)v->ptr)[i] 566 #define EURYDICE_VEC_LEN(v, t) (v)->len 567 568 /* TODO: remove GCC-isms */ 569 570 #define EURYDICE_REPLACE(ptr, new_v, t) \ 571 ({ \ 572 t old_v = *ptr; \ 573 *ptr = new_v; \ 574 old_v; \ 575 })