hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

store.ha (14338B)


      1 // License: MPL-2.0
      2 // (c) 2021 Alexey Yerin <yyp@disroot.org>
      3 // (c) 2021 Drew DeVault <sir@cmpwn.com>
      4 // (c) 2021 Eyal 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::CHAR =>
    130 			return &builtin_char;
    131 		case builtin::F32 =>
    132 			return &builtin_f32;
    133 		case builtin::F64 =>
    134 			return &builtin_f64;
    135 		case builtin::I8 =>
    136 			return &builtin_i8;
    137 		case builtin::I16 =>
    138 			return &builtin_i16;
    139 		case builtin::I32 =>
    140 			return &builtin_i32;
    141 		case builtin::I64 =>
    142 			return &builtin_i64;
    143 		case builtin::RUNE =>
    144 			return &builtin_rune;
    145 		case builtin::U8 =>
    146 			return &builtin_u8;
    147 		case builtin::U16 =>
    148 			return &builtin_u16;
    149 		case builtin::U32 =>
    150 			return &builtin_u32;
    151 		case builtin::U64 =>
    152 			return &builtin_u64;
    153 		case builtin::VOID =>
    154 			return &builtin_void;
    155 		case => void;
    156 		};
    157 	case => void;
    158 	};
    159 
    160 	const id = hash(&ty);
    161 	let bucket = &store.map[id % BUCKETS];
    162 	for (let i = 0z; i < len(bucket); i += 1) {
    163 		if (bucket[i].id == id) {
    164 			type_finish(&ty);
    165 			return &bucket[i];
    166 		};
    167 	};
    168 	ty.id = id;
    169 	append(bucket, ty);
    170 	return &bucket[len(bucket) - 1];
    171 };
    172 
    173 fn fromast(store: *typestore, atype: *ast::_type) (_type | deferred | error) = {
    174 	let sz = SIZE_UNDEFINED, align = SIZE_UNDEFINED;
    175 	const repr = match (atype.repr) {
    176 	case let a: ast::alias_type =>
    177 		// TODO: This is incomplete
    178 		assert(!a.unwrap);
    179 		yield alias {
    180 			id = ast::ident_dup(a.ident),
    181 			secondary = null,
    182 		};
    183 	case let b: ast::builtin_type =>
    184 		// TODO: Tuple unpacking could improve this
    185 		yield switch (b) {
    186 		case ast::builtin_type::BOOL =>
    187 			sz = store.arch._int;
    188 			align = store.arch._int;
    189 			yield builtin::BOOL;
    190 		case ast::builtin_type::CHAR =>
    191 			sz = 1; align = 1;
    192 			yield builtin::CHAR;
    193 		case ast::builtin_type::F32 =>
    194 			sz = 4; align = 4;
    195 			yield builtin::F32;
    196 		case ast::builtin_type::F64 =>
    197 			sz = 8; align = 8;
    198 			yield builtin::F64;
    199 		case ast::builtin_type::I16 =>
    200 			sz = 2; align = 2;
    201 			yield builtin::I16;
    202 		case ast::builtin_type::I32 =>
    203 			sz = 4; align = 4;
    204 			yield builtin::I32;
    205 		case ast::builtin_type::I64 =>
    206 			sz = 8; align = 8;
    207 			yield builtin::I64;
    208 		case ast::builtin_type::I8 =>
    209 			sz = 1; align = 1;
    210 			yield builtin::I8;
    211 		case ast::builtin_type::INT =>
    212 			sz = store.arch._int;
    213 			align = store.arch._int;
    214 			yield builtin::INT;
    215 		case ast::builtin_type::RUNE =>
    216 			sz = 4; align = 4;
    217 			yield builtin::RUNE;
    218 		case ast::builtin_type::SIZE =>
    219 			sz = store.arch._size;
    220 			align = store.arch._size;
    221 			yield builtin::SIZE;
    222 		case ast::builtin_type::STR =>
    223 			sz = store.arch._pointer;
    224 			sz += sz % store.arch._size + store.arch._size;
    225 			sz += store.arch._size;
    226 			align = if (store.arch._size > store.arch._pointer)
    227 					store.arch._size
    228 				else
    229 					store.arch._pointer;
    230 			yield builtin::STR;
    231 		case ast::builtin_type::U16 =>
    232 			sz = 2; align = 2;
    233 			yield builtin::U16;
    234 		case ast::builtin_type::U32 =>
    235 			sz = 4; align = 4;
    236 			yield builtin::U32;
    237 		case ast::builtin_type::U64 =>
    238 			sz = 8; align = 8;
    239 			yield builtin::U64;
    240 		case ast::builtin_type::U8 =>
    241 			sz = 1; align = 1;
    242 			yield builtin::U8;
    243 		case ast::builtin_type::UINT =>
    244 			sz = store.arch._int;
    245 			align = store.arch._int;
    246 			yield builtin::UINT;
    247 		case ast::builtin_type::UINTPTR =>
    248 			sz = store.arch._pointer;
    249 			align = store.arch._pointer;
    250 			yield builtin::UINTPTR;
    251 		case ast::builtin_type::VOID =>
    252 			sz = 0; align = 0;
    253 			yield builtin::VOID;
    254 		case ast::builtin_type::NULL =>
    255 			sz = store.arch._pointer;
    256 			align = store.arch._pointer;
    257 			yield builtin::NULL;
    258 		case ast::builtin_type::ICONST, ast::builtin_type::FCONST =>
    259 			abort(); // TODO?
    260 		};
    261 	case let f: ast::func_type =>
    262 		yield func_from_ast(store, &f)?;
    263 	case let p: ast::pointer_type =>
    264 		sz = store.arch._pointer;
    265 		align = store.arch._pointer;
    266 		yield pointer {
    267 			referent = lookup(store, p.referent)?,
    268 			flags = p.flags: pointer_flags,
    269 		};
    270 	case let st: ast::struct_type =>
    271 		let st = struct_from_ast(store, st, false)?;
    272 		sz = 0; align = 0;
    273 		for (let i = 0z; i < len(st.fields); i += 1) {
    274 			const field = st.fields[i];
    275 			if (field.offs + field._type.sz > sz) {
    276 				sz = field.offs + field._type.sz;
    277 			};
    278 			if (field._type.align > align) {
    279 				align = field._type.align;
    280 			};
    281 		};
    282 		yield st;
    283 	case let un: ast::union_type =>
    284 		let st = struct_from_ast(store, un, true)?;
    285 		sz = 0; align = 0;
    286 		for (let i = 0z; i < len(st.fields); i += 1) {
    287 			const field = st.fields[i];
    288 			if (field.offs + field._type.sz > sz) {
    289 				sz = field.offs + field._type.sz;
    290 			};
    291 			if (field._type.align > align) {
    292 				align = field._type.align;
    293 			};
    294 		};
    295 		yield st;
    296 	case let ta: ast::tagged_type =>
    297 		let ta = tagged_from_ast(store, ta)?;
    298 		sz = 0; align = 0;
    299 		for (let i = 0z; i < len(ta); i += 1) {
    300 			if (ta[i].sz > sz) {
    301 				sz = ta[i].sz;
    302 			};
    303 			if (ta[i].align > align) {
    304 				align = ta[i].align;
    305 			};
    306 		};
    307 		if (store.arch._int > align) {
    308 			align = store.arch._int;
    309 		};
    310 		sz += store.arch._int % align + store.arch._int;
    311 		yield ta;
    312 	case let tu: ast::tuple_type =>
    313 		let tu = tuple_from_ast(store, tu)?;
    314 		sz = 0; align = 0;
    315 		for (let i = 0z; i < len(tu); i += 1) {
    316 			const value = tu[i];
    317 			if (value.offs + value._type.sz > sz) {
    318 				sz = value.offs + value._type.sz;
    319 			};
    320 			if (value._type.align > align) {
    321 				align = value._type.align;
    322 			};
    323 		};
    324 		yield tu;
    325 	case let lt: ast::list_type =>
    326 		let r = list_from_ast(store, &lt)?;
    327 		sz = r.0;
    328 		align = r.1;
    329 		yield r.2;
    330 	case let et: ast::enum_type =>
    331 		abort(); // TODO
    332 	};
    333 	if (sz != SIZE_UNDEFINED && sz != 0 && sz % align != 0) {
    334 		sz += align - (sz - align) % align;
    335 	};
    336 	return _type {
    337 		id = 0, // filled in later
    338 		flags = atype.flags: flags,
    339 		repr = repr,
    340 		sz = sz,
    341 		align = align,
    342 	};
    343 };
    344 
    345 fn func_from_ast(
    346 	store: *typestore,
    347 	ft: *ast::func_type,
    348 ) (func | deferred | error) = {
    349 	let f = func {
    350 		result = lookup(store, ft.result)?,
    351 		variadism = switch (ft.variadism) {
    352 		case ast::variadism::NONE =>
    353 			yield variadism::NONE;
    354 		case ast::variadism::C =>
    355 			yield variadism::C;
    356 		case ast::variadism::HARE =>
    357 			yield variadism::HARE;
    358 		},
    359 		flags = 0,
    360 		params = alloc([], len(ft.params)),
    361 	};
    362 	if (ft.attrs & ast::func_attrs::NORETURN != 0) {
    363 		f.flags |= func_flags::NORETURN;
    364 	};
    365 	for (let i = 0z; i < len(ft.params); i += 1) {
    366 		append(f.params, lookup(store, ft.params[i]._type)?);
    367 	};
    368 	return f;
    369 };
    370 
    371 fn list_from_ast(
    372 	store: *typestore,
    373 	lt: *ast::list_type
    374 ) ((size, size, (slice | array)) | deferred | error) = {
    375 	let sz = SIZE_UNDEFINED, align = SIZE_UNDEFINED;
    376 	let memb = lookup(store, lt.members)?;
    377 	let t = match (lt.length) {
    378 	case ast::len_slice =>
    379 		sz = store.arch._pointer;
    380 		if (sz % store.arch._size != 0) {
    381 			sz += store.arch._size - (sz % store.arch._size);
    382 		};
    383 		sz += store.arch._size * 2;
    384 		align = if (store.arch._pointer > store.arch._size)
    385 				store.arch._pointer
    386 			else store.arch._size;
    387 		yield memb: slice;
    388 	case (ast::len_unbounded | ast::len_contextual) =>
    389 		// Note: contextual length is handled by hare::unit when
    390 		// initializing bindings. We treat it like unbounded here and
    391 		// it's fixed up later on.
    392 		align = memb.align;
    393 		yield array {
    394 			length = SIZE_UNDEFINED,
    395 			member = memb,
    396 		};
    397 	case let ex: *ast::expr =>
    398 		const resolv = match (store.resolve) {
    399 		case null =>
    400 			return noresolver;
    401 		case let r: *resolver =>
    402 			yield r;
    403 		};
    404 		const length = resolv(store.rstate, store, ex)?;
    405 		sz = memb.sz * length;
    406 		assert(sz / length == memb.sz, "overflow");
    407 		align = memb.align;
    408 		yield array {
    409 			length = length,
    410 			member = memb,
    411 		};
    412 	};
    413 	return (sz, align, t);
    414 };
    415 
    416 fn _struct_from_ast(
    417 	store: *typestore,
    418 	membs: []ast::struct_member,
    419 	is_union: bool,
    420 	fields: *[]struct_field,
    421 	offs: *size,
    422 ) (void | deferred | error) = {
    423 	const nfields = len(fields);
    424 	for (let i = 0z; i < len(membs); i += 1) {
    425 		*offs = match (membs[i]._offset) {
    426 		case let ex: *ast::expr =>
    427 			yield match (store.resolve) {
    428 			case null =>
    429 				return noresolver;
    430 			case let res: *resolver =>
    431 				yield res(store.rstate, store, ex)?;
    432 			};
    433 		case null =>
    434 			yield *offs;
    435 		};
    436 
    437 		const memb = match (membs[i].member) {
    438 		case let se: ast::struct_embedded =>
    439 			let membs: []ast::struct_member = match (se.repr) {
    440 			case let st: ast::struct_type =>
    441 				yield st;
    442 			case let ut: ast::union_type =>
    443 				yield ut;
    444 			case =>
    445 				abort(); // Invariant
    446 			};
    447 			_struct_from_ast(store, membs,
    448 				se.repr is ast::union_type,
    449 				fields, offs)?;
    450 			continue;
    451 		case let se: ast::struct_alias =>
    452 			abort(); // TODO
    453 		case let sf: ast::struct_field =>
    454 			yield sf;
    455 		};
    456 
    457 		const _type = lookup(store, memb._type)?;
    458 		if (*offs % _type.align != 0) {
    459 			*offs += _type.align - (*offs % _type.align);
    460 		};
    461 
    462 		append(fields, struct_field {
    463 			name = memb.name,
    464 			offs = *offs,
    465 			_type = _type,
    466 		});
    467 
    468 		if (!is_union) {
    469 			*offs += _type.sz;
    470 		};
    471 	};
    472 
    473 	if (is_union) {
    474 		let max = 0z;
    475 		for (let i = nfields; i < len(fields); i += 1) {
    476 			if (fields[i].offs + fields[i]._type.sz > max) {
    477 				max = fields[i].offs + fields[i]._type.sz;
    478 			};
    479 		};
    480 		*offs = max;
    481 	};
    482 };
    483 
    484 fn struct_from_ast(
    485 	store: *typestore,
    486 	membs: []ast::struct_member,
    487 	is_union: bool,
    488 ) (_struct | deferred | error) = {
    489 	let fields: []struct_field = [];
    490 	let offs = 0z;
    491 	_struct_from_ast(store, membs, is_union, &fields, &offs)?;
    492 	sort::sort(fields, size(struct_field), &field_cmp);
    493 	return _struct {
    494 		kind = if (is_union) struct_union::UNION else struct_union::STRUCT,
    495 		fields = fields,
    496 	};
    497 };
    498 
    499 fn tagged_collect(
    500 	store: *typestore,
    501 	atype: ast::tagged_type,
    502 	types: *[]const *_type,
    503 ) (void | deferred | error) = {
    504 	for (let i = 0z; i < len(atype); i += 1) match (atype[i].repr) {
    505 	case let ta: ast::tagged_type =>
    506 		tagged_collect(store, ta, types)?;
    507 	case =>
    508 		append(types, lookup(store, atype[i])?);
    509 	};
    510 };
    511 
    512 fn tagged_cmp(a: const *void, b: const *void) int = {
    513 	const a = a: const **_type, b = b: const **_type;
    514 	return if (a.id < b.id) -1 else if (a.id == b.id) 0 else 1;
    515 };
    516 
    517 fn tagged_from_ast(
    518 	store: *typestore,
    519 	atype: ast::tagged_type,
    520 ) (tagged | deferred | error) = {
    521 	let types: []const *_type = [];
    522 	//defer! free(types);
    523 	tagged_collect(store, atype, &types)?;
    524 	sort::sort(types, size(const *_type), &tagged_cmp);
    525 	for (let i = 1z; i < len(types); i += 1) {
    526 		if (types[i].id == types[i - 1].id) {
    527 			delete(types[i]);
    528 			i -= 1;
    529 		};
    530 	};
    531 	// TODO: Handle this gracefully
    532 	assert(len(types) > 1);
    533 	return types;
    534 };
    535 
    536 fn tuple_from_ast(
    537 	store: *typestore,
    538 	membs: ast::tuple_type,
    539 ) (tuple | deferred | error) = {
    540 	let values: []tuple_value = [];
    541 	let offs = 0z;
    542 	for (let i = 0z; i < len(membs); i += 1) {
    543 		const val = membs[i];
    544 		const vtype = lookup(store, val)?;
    545 
    546 		if (offs % vtype.align != 0) {
    547 			offs += vtype.align - (offs % vtype.align);
    548 		};
    549 
    550 		append(values, tuple_value {
    551 			_type = vtype,
    552 			offs = offs,
    553 		});
    554 
    555 		offs += vtype.sz;
    556 	};
    557 	return values;
    558 };
    559 
    560 fn field_cmp(a: const *void, b: const *void) int = {
    561 	const a = a: const *struct_field, b = b: *const struct_field;
    562 	return strings::compare(a.name, b.name);
    563 };
    564 
    565 fn type_finish(t: *_type) void = {
    566 	match (t.repr) {
    567 	case let a: alias =>
    568 		ast::ident_free(a.id);
    569 	case array => void;
    570 	case builtin => void;
    571 	case let e: _enum =>
    572 		free(e.values);
    573 	case let f: func =>
    574 		free(f.params);
    575 	case pointer => void;
    576 	case let s: slice => void;
    577 	case let st: _struct =>
    578 		free(st.fields);
    579 	case let tu: tuple =>
    580 		free(tu);
    581 	case let ta: tagged =>
    582 		free(ta);
    583 	};
    584 };