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