store.ha (14866B)
1 // SPDX-License-Identifier: MPL-2.0 2 // (c) Hare authors <https://harelang.org> 3 4 use errors; 5 use hare::ast; 6 use sort; 7 use strings; 8 9 export def BUCKETS: size = 65535; 10 11 // A function which evaluates a [[hare::ast::expr]], providing either a size 12 // result or an error. 13 export type resolver = fn( 14 rstate: nullable *opaque, 15 store: *typestore, 16 expr: const *ast::expr, 17 ) (size | deferred | error); 18 19 export type typestore = struct { 20 // This hash map provides the canonical address for all types owned by 21 // this type store. Any type which has a reference to another type has 22 // borrowed it from this map. 23 map: [BUCKETS][]_type, 24 25 arch: arch, 26 resolve: nullable *resolver, 27 rstate: nullable *opaque, 28 }; 29 30 // Initializes a new type store. Optionally, provide a function which 31 // type-checks and evaluates an [[hare::ast::expr]]. If a resolver is not 32 // provided, looking up types with an expression component (e.g. [2 + 2]int) 33 // will return [[noresolver]]. 34 export fn store( 35 arch: arch, 36 resolver: nullable *resolver, 37 rstate: nullable *opaque, 38 ) *typestore = alloc(typestore { 39 arch = arch, 40 resolve = resolver, 41 rstate = rstate, 42 ... 43 }); 44 45 // Frees state associated with a [[typestore]]. 46 export fn store_free(store: *typestore) void = { 47 for (let i = 0z; i < len(store.map); i += 1) { 48 for (let j = 0z; j < len(store.map[i]); j += 1) { 49 type_finish(&store.map[i][j]); 50 }; 51 free(store.map[i]); 52 }; 53 free(store); 54 }; 55 56 // Creates a new type alias. 57 export fn newalias( 58 store: *typestore, 59 ident: const ast::ident, 60 of: const *_type, 61 ) const *_type = { 62 const atype: _type = _type { 63 flags = of.flags, 64 repr = alias { 65 id = ast::ident_dup(ident), 66 secondary = of, 67 }, 68 id = 0, 69 sz = of.sz, 70 _align = of._align, 71 }; 72 const id = hash(&atype); 73 atype.id = id; 74 75 // Fill in forward-referenced aliases 76 match (lookup(store, &ast::_type { 77 repr = ast::alias_type { 78 unwrap = false, 79 ident = ident, 80 }, 81 ... 82 })) { 83 case error => void; 84 case deferred => void; 85 case let ty: const *_type => 86 let ty = ty: *_type; 87 *ty = atype; 88 return ty; 89 }; 90 91 // Or create a new alias 92 let bucket = &store.map[id % BUCKETS]; 93 append(bucket, atype); 94 return &bucket[len(bucket) - 1]; 95 }; 96 97 // Returned from [[lookup]] when we are unable to resolve this type, but it does 98 // not necessarily have an error. This occurs when a type includes an unknown 99 // forward reference. 100 export type deferred = !void; 101 102 // A resolver function was not provided to [[store]], but was required to look 103 // up this type. 104 export type noresolver = !void; 105 106 // All possible errors for [[lookup]]. 107 export type error = !(noresolver | errors::opaque_); 108 109 // Convert an error into a human-friendly string. 110 export fn strerror(err: error) const str = match (err) { 111 case noresolver => 112 return "Resolver function not provided, but required"; 113 case let err: errors::opaque_ => 114 return errors::strerror(err); 115 }; 116 117 // Retrieves a [[_type]] for a given [[hare::ast::_type]]. 118 export fn lookup( 119 store: *typestore, 120 ty: *ast::_type, 121 ) (const *_type | deferred | error) = { 122 const ty = fromast(store, ty)?; 123 if (ty.flags == 0) match (ty.repr) { 124 case let b: builtin => 125 switch (b) { 126 case builtin::F32 => 127 return &builtin_f32; 128 case builtin::F64 => 129 return &builtin_f64; 130 case builtin::I8 => 131 return &builtin_i8; 132 case builtin::I16 => 133 return &builtin_i16; 134 case builtin::I32 => 135 return &builtin_i32; 136 case builtin::I64 => 137 return &builtin_i64; 138 case builtin::OPAQUE => 139 return &builtin_opaque; 140 case builtin::RUNE => 141 return &builtin_rune; 142 case builtin::U8 => 143 return &builtin_u8; 144 case builtin::U16 => 145 return &builtin_u16; 146 case builtin::U32 => 147 return &builtin_u32; 148 case builtin::U64 => 149 return &builtin_u64; 150 case builtin::VOID => 151 return &builtin_void; 152 case builtin::DONE => 153 return &builtin_done; 154 case => void; 155 }; 156 case => void; 157 }; 158 159 const id = hash(&ty); 160 let bucket = &store.map[id % BUCKETS]; 161 for (let i = 0z; i < len(bucket); i += 1) { 162 if (bucket[i].id == id) { 163 type_finish(&ty); 164 return &bucket[i]; 165 }; 166 }; 167 ty.id = id; 168 append(bucket, ty); 169 return &bucket[len(bucket) - 1]; 170 }; 171 172 fn fromast(store: *typestore, atype: *ast::_type) (_type | deferred | error) = { 173 let sz = SIZE_UNDEFINED, _align = SIZE_UNDEFINED; 174 const repr = match (atype.repr) { 175 case let a: ast::alias_type => 176 // TODO: This is incomplete 177 assert(!a.unwrap); 178 yield alias { 179 id = ast::ident_dup(a.ident), 180 secondary = null, 181 }; 182 case let b: ast::builtin_type => 183 // TODO: Tuple unpacking could improve this 184 yield switch (b) { 185 case ast::builtin_type::BOOL => 186 sz = store.arch._int; 187 _align = store.arch._int; 188 yield builtin::BOOL; 189 case ast::builtin_type::DONE => 190 sz = 0; _align = 0; 191 yield builtin::DONE; 192 case ast::builtin_type::F32 => 193 sz = 4; _align = 4; 194 yield builtin::F32; 195 case ast::builtin_type::F64 => 196 sz = 8; _align = 8; 197 yield builtin::F64; 198 case ast::builtin_type::I16 => 199 sz = 2; _align = 2; 200 yield builtin::I16; 201 case ast::builtin_type::I32 => 202 sz = 4; _align = 4; 203 yield builtin::I32; 204 case ast::builtin_type::I64 => 205 sz = 8; _align = 8; 206 yield builtin::I64; 207 case ast::builtin_type::I8 => 208 sz = 1; _align = 1; 209 yield builtin::I8; 210 case ast::builtin_type::INT => 211 sz = store.arch._int; 212 _align = store.arch._int; 213 yield builtin::INT; 214 case ast::builtin_type::RUNE => 215 sz = 4; _align = 4; 216 yield builtin::RUNE; 217 case ast::builtin_type::SIZE => 218 sz = store.arch._size; 219 _align = store.arch._size; 220 yield builtin::SIZE; 221 case ast::builtin_type::STR => 222 sz = store.arch._pointer; 223 sz += sz % store.arch._size + store.arch._size; 224 sz += store.arch._size; 225 _align = if (store.arch._size > store.arch._pointer) 226 store.arch._size 227 else 228 store.arch._pointer; 229 yield builtin::STR; 230 case ast::builtin_type::U16 => 231 sz = 2; _align = 2; 232 yield builtin::U16; 233 case ast::builtin_type::U32 => 234 sz = 4; _align = 4; 235 yield builtin::U32; 236 case ast::builtin_type::U64 => 237 sz = 8; _align = 8; 238 yield builtin::U64; 239 case ast::builtin_type::U8 => 240 sz = 1; _align = 1; 241 yield builtin::U8; 242 case ast::builtin_type::UINT => 243 sz = store.arch._int; 244 _align = store.arch._int; 245 yield builtin::UINT; 246 case ast::builtin_type::UINTPTR => 247 sz = store.arch._pointer; 248 _align = store.arch._pointer; 249 yield builtin::UINTPTR; 250 case ast::builtin_type::VOID => 251 sz = 0; _align = 0; 252 yield builtin::VOID; 253 case ast::builtin_type::NULL => 254 sz = store.arch._pointer; 255 _align = store.arch._pointer; 256 yield builtin::NULL; 257 case ast::builtin_type::ICONST, ast::builtin_type::FCONST, 258 ast::builtin_type::RCONST => 259 abort(); // TODO? 260 case ast::builtin_type::OPAQUE => 261 sz = SIZE_UNDEFINED; 262 _align = SIZE_UNDEFINED; 263 yield builtin::OPAQUE; 264 case ast::builtin_type::NEVER => 265 sz = SIZE_UNDEFINED; 266 _align = SIZE_UNDEFINED; 267 yield builtin::NEVER; 268 case ast::builtin_type::VALIST => 269 sz = store.arch.valist_size; 270 _align = store.arch.valist_align; 271 yield builtin::VALIST; 272 }; 273 case let f: ast::func_type => 274 yield func_from_ast(store, &f)?; 275 case let p: ast::pointer_type => 276 sz = store.arch._pointer; 277 _align = store.arch._pointer; 278 yield pointer { 279 referent = lookup(store, p.referent)?, 280 flags = p.flags: pointer_flag, 281 }; 282 case let st: ast::struct_type => 283 let st = struct_from_ast(store, st, false)?; 284 sz = 0; _align = 0; 285 for (let i = 0z; i < len(st.fields); i += 1) { 286 const field = st.fields[i]; 287 if (field.offs + field._type.sz > sz) { 288 sz = field.offs + field._type.sz; 289 }; 290 if (field._type._align > _align) { 291 _align = field._type._align; 292 }; 293 }; 294 yield st; 295 case let un: ast::union_type => 296 let st = struct_from_ast(store, un, true)?; 297 sz = 0; _align = 0; 298 for (let i = 0z; i < len(st.fields); i += 1) { 299 const field = st.fields[i]; 300 if (field.offs + field._type.sz > sz) { 301 sz = field.offs + field._type.sz; 302 }; 303 if (field._type._align > _align) { 304 _align = field._type._align; 305 }; 306 }; 307 yield st; 308 case let ta: ast::tagged_type => 309 let ta = tagged_from_ast(store, ta)?; 310 sz = 0; _align = 0; 311 for (let i = 0z; i < len(ta); i += 1) { 312 if (ta[i].sz > sz) { 313 sz = ta[i].sz; 314 }; 315 if (ta[i]._align > _align) { 316 _align = ta[i]._align; 317 }; 318 }; 319 if (store.arch._int > _align) { 320 _align = store.arch._int; 321 }; 322 sz += store.arch._int % _align + store.arch._int; 323 yield ta; 324 case let tu: ast::tuple_type => 325 let tu = tuple_from_ast(store, tu)?; 326 sz = 0; _align = 0; 327 for (let i = 0z; i < len(tu); i += 1) { 328 const value = tu[i]; 329 if (value.offs + value._type.sz > sz) { 330 sz = value.offs + value._type.sz; 331 }; 332 if (value._type._align > _align) { 333 _align = value._type._align; 334 }; 335 }; 336 yield tu; 337 case let lt: ast::list_type => 338 let r = list_from_ast(store, <)?; 339 sz = r.0; 340 _align = r.1; 341 yield r.2; 342 case let et: ast::enum_type => 343 abort(); // TODO 344 }; 345 if (sz != SIZE_UNDEFINED && sz != 0 && sz % _align != 0) { 346 sz += _align - (sz - _align) % _align; 347 }; 348 return _type { 349 id = 0, // filled in later 350 flags = atype.flags: flag, 351 repr = repr, 352 sz = sz, 353 _align = _align, 354 }; 355 }; 356 357 fn func_from_ast( 358 store: *typestore, 359 ft: *ast::func_type, 360 ) (func | deferred | error) = { 361 let f = func { 362 result = lookup(store, ft.result)?, 363 variadism = switch (ft.variadism) { 364 case ast::variadism::NONE => 365 yield variadism::NONE; 366 case ast::variadism::C => 367 yield variadism::C; 368 case ast::variadism::HARE => 369 yield variadism::HARE; 370 }, 371 params = alloc([], len(ft.params)), 372 }; 373 for (let i = 0z; i < len(ft.params); i += 1) { 374 append(f.params, lookup(store, ft.params[i]._type)?); 375 }; 376 return f; 377 }; 378 379 fn list_from_ast( 380 store: *typestore, 381 lt: *ast::list_type 382 ) ((size, size, (slice | array)) | deferred | error) = { 383 let sz = SIZE_UNDEFINED, _align = SIZE_UNDEFINED; 384 let memb = lookup(store, lt.members)?; 385 let t = match (lt.length) { 386 case ast::len_slice => 387 sz = store.arch._pointer; 388 if (sz % store.arch._size != 0) { 389 sz += store.arch._size - (sz % store.arch._size); 390 }; 391 sz += store.arch._size * 2; 392 _align = if (store.arch._pointer > store.arch._size) 393 store.arch._pointer 394 else store.arch._size; 395 yield memb: slice; 396 case (ast::len_unbounded | ast::len_contextual) => 397 // Note: contextual length is handled by hare::unit when 398 // initializing bindings. We treat it like unbounded here and 399 // it's fixed up later on. 400 _align = memb._align; 401 yield array { 402 length = SIZE_UNDEFINED, 403 member = memb, 404 }; 405 case let ex: *ast::expr => 406 const resolv = match (store.resolve) { 407 case null => 408 return noresolver; 409 case let r: *resolver => 410 yield r; 411 }; 412 const length = resolv(store.rstate, store, ex)?; 413 sz = memb.sz * length; 414 assert(sz / length == memb.sz, "overflow"); 415 _align = memb._align; 416 yield array { 417 length = length, 418 member = memb, 419 }; 420 }; 421 return (sz, _align, t); 422 }; 423 424 fn _struct_from_ast( 425 store: *typestore, 426 atype: ast::struct_union_type, 427 is_union: bool, 428 fields: *[]struct_field, 429 offs: *size, 430 ) (void | deferred | error) = { 431 const nfields = len(fields); 432 const membs = match(atype) { 433 case let atype: ast::struct_type => 434 yield atype.members; 435 case let atype: ast::union_type => 436 yield atype: []ast::struct_member; 437 }; 438 for (let i = 0z; i < len(membs); i += 1) { 439 *offs = match (membs[i]._offset) { 440 case let ex: *ast::expr => 441 yield match (store.resolve) { 442 case null => 443 return noresolver; 444 case let res: *resolver => 445 yield res(store.rstate, store, ex)?; 446 }; 447 case null => 448 yield *offs; 449 }; 450 451 const memb = match (membs[i].member) { 452 case let se: ast::struct_embedded => 453 let membs: []ast::struct_member = match (se.repr) { 454 case let st: ast::struct_type => 455 yield st.members; 456 case let ut: ast::union_type => 457 yield ut; 458 case => 459 abort(); // Invariant 460 }; 461 _struct_from_ast(store, membs, 462 se.repr is ast::union_type, 463 fields, offs)?; 464 continue; 465 case let se: ast::struct_alias => 466 abort(); // TODO 467 case let sf: ast::struct_field => 468 yield sf; 469 }; 470 471 const _type = lookup(store, memb._type)?; 472 if (*offs % _type._align != 0) { 473 *offs += _type._align - (*offs % _type._align); 474 }; 475 476 append(fields, struct_field { 477 name = memb.name, 478 offs = *offs, 479 _type = _type, 480 }); 481 482 if (!is_union) { 483 *offs += _type.sz; 484 }; 485 }; 486 487 if (is_union) { 488 let max = 0z; 489 for (let i = nfields; i < len(fields); i += 1) { 490 if (fields[i].offs + fields[i]._type.sz > max) { 491 max = fields[i].offs + fields[i]._type.sz; 492 }; 493 }; 494 *offs = max; 495 }; 496 }; 497 498 fn struct_from_ast( 499 store: *typestore, 500 atype: ast::struct_union_type, 501 is_union: bool, 502 ) (_struct | deferred | error) = { 503 let fields: []struct_field = []; 504 let offs = 0z; 505 _struct_from_ast(store, atype, is_union, &fields, &offs)?; 506 sort::sort(fields, size(struct_field), &field_cmp); 507 return _struct { 508 kind = if (is_union) struct_union::UNION else struct_union::STRUCT, 509 fields = fields, 510 }; 511 }; 512 513 fn tagged_collect( 514 store: *typestore, 515 atype: ast::tagged_type, 516 types: *[]const *_type, 517 ) (void | deferred | error) = { 518 for (let i = 0z; i < len(atype); i += 1) match (atype[i].repr) { 519 case let ta: ast::tagged_type => 520 tagged_collect(store, ta, types)?; 521 case => 522 append(types, lookup(store, atype[i])?); 523 }; 524 }; 525 526 fn tagged_cmp(a: const *opaque, b: const *opaque) int = { 527 const a = a: const **_type, b = b: const **_type; 528 return if (a.id < b.id) -1 else if (a.id == b.id) 0 else 1; 529 }; 530 531 fn tagged_from_ast( 532 store: *typestore, 533 atype: ast::tagged_type, 534 ) (tagged | deferred | error) = { 535 let types: []const *_type = []; 536 //defer! free(types); 537 tagged_collect(store, atype, &types)?; 538 sort::sort(types, size(const *_type), &tagged_cmp); 539 for (let i = 1z; i < len(types); i += 1) { 540 if (types[i].id == types[i - 1].id) { 541 delete(types[i]); 542 i -= 1; 543 }; 544 }; 545 // TODO: Handle this gracefully 546 assert(len(types) > 1); 547 return types; 548 }; 549 550 fn tuple_from_ast( 551 store: *typestore, 552 membs: ast::tuple_type, 553 ) (tuple | deferred | error) = { 554 let values: []tuple_value = []; 555 let offs = 0z; 556 for (let i = 0z; i < len(membs); i += 1) { 557 const val = membs[i]; 558 const vtype = lookup(store, val)?; 559 560 if (offs % vtype._align != 0) { 561 offs += vtype._align - (offs % vtype._align); 562 }; 563 564 append(values, tuple_value { 565 _type = vtype, 566 offs = offs, 567 }); 568 569 offs += vtype.sz; 570 }; 571 return values; 572 }; 573 574 fn field_cmp(a: const *opaque, b: const *opaque) int = { 575 const a = a: const *struct_field, b = b: *const struct_field; 576 return strings::compare(a.name, b.name); 577 }; 578 579 fn type_finish(t: *_type) void = { 580 match (t.repr) { 581 case let a: alias => 582 ast::ident_free(a.id); 583 case array => void; 584 case builtin => void; 585 case let e: _enum => 586 free(e.values); 587 case let f: func => 588 free(f.params); 589 case pointer => void; 590 case let s: slice => void; 591 case let st: _struct => 592 free(st.fields); 593 case let tu: tuple => 594 free(tu); 595 case let ta: tagged => 596 free(ta); 597 }; 598 };