commit 96ced5c8c0e9619026e0c9343a257584a6d18230
parent c5b4c37c373d7a891c1b743da6408906b141f701
Author: Drew DeVault <sir@cmpwn.com>
Date: Thu, 29 Apr 2021 09:32:22 -0400
hare::types: initial pass for new module
Signed-off-by: Drew DeVault <sir@cmpwn.com>
Diffstat:
6 files changed, 205 insertions(+), 3 deletions(-)
diff --git a/hare/ast/ident.ha b/hare/ast/ident.ha
@@ -1,3 +1,5 @@
+use strings;
+
// Identifies a single object, e.g. foo::bar::baz.
export type ident = []str;
@@ -27,3 +29,12 @@ export fn ident_eq(a: ident, b: ident) bool = {
};
return true;
};
+
+// Duplicates an [[ident]].
+export fn ident_dup(id: ident) ident = {
+ let new: ident = alloc([], len(id));
+ for (let i = 0z; i < len(id); i += 1) {
+ append(new, strings::dup(id[0]));
+ };
+ return new;
+};
diff --git a/hare/types/hash.ha b/hare/types/hash.ha
@@ -0,0 +1,75 @@
+use endian;
+use hash::fnv;
+use hash;
+use strings;
+use fmt;
+
+// Keep ordered with respect to bootstrap harec:include/types.h
+type storage = enum u8 {
+ BOOL, CHAR, ENUM, F32, F64, FCONST, I16, I32, I64, I8, ICONST, INT,
+ NULL, RUNE, SIZE, U16, U32, U64, U8, UINT, UINTPTR, VOID, ALIAS, ARRAY,
+ FUNCTION, POINTER, SLICE, STRING, STRUCT, TAGGED, TUPLE, UNION,
+};
+
+fn type_storage(t: *_type) u8 = match (t._type) {
+ alias => storage::ALIAS,
+ t: builtin => switch (t) {
+ builtin::BOOL => storage::BOOL,
+ builtin::CHAR => storage::CHAR,
+ builtin::F32 => storage::F32,
+ builtin::F64 => storage::F64,
+ builtin::I16 => storage::I16,
+ builtin::I32 => storage::I32,
+ builtin::I64 => storage::I64,
+ builtin::I8 => storage::I8,
+ builtin::INT => storage::INT,
+ builtin::NULL => storage::NULL,
+ builtin::RUNE => storage::RUNE,
+ builtin::SIZE => storage::SIZE,
+ builtin::STR => storage::STRING,
+ builtin::U16 => storage::U16,
+ builtin::U32 => storage::U32,
+ builtin::U64 => storage::U64,
+ builtin::U8 => storage::U8,
+ builtin::UINT => storage::UINT,
+ builtin::UINTPTR => storage::UINTPTR,
+ builtin::VOID => storage::VOID,
+ },
+ * => abort(), // TODO
+};
+
+fn write8(h: *hash::hash, u: u8) void = {
+ let buf = &u: *[*]u8;
+ hash::write(h, buf[..1]);
+};
+
+// Returns the hash of a type. These hashes are deterministic and universally
+// unique: different computers will generate the same hash for the same type.
+export fn hash(t: *_type) u32 = {
+ let hash = fnv::fnv32a();
+ defer hash::close(hash);
+ write8(hash, type_storage(t));
+ write8(hash, t.flags);
+
+ match (t._type) {
+ a: alias => for (let i = 0z; i < len(a); i += 1) {
+ hash::write(hash, strings::toutf8(a[i]));
+ write8(hash, 0);
+ },
+ builtin => void,
+ };
+
+ return fnv::sum32(hash);
+};
+
+@test fn hash() void = {
+ // Test a few samples for ABI compatibility with harec
+ let sample = _type {
+ flags = flags::NONE,
+ _type = builtin::STR,
+ };
+ fmt::errorfln("{}", hash(&sample))!;
+ assert(hash(&sample) == 3350498318);
+
+ // TODO: more samples
+};
diff --git a/hare/types/store.ha b/hare/types/store.ha
@@ -0,0 +1,52 @@
+use hare::ast;
+
+export def BUCKETS: size = 65535;
+
+// A type store. Holds singletons for types in a hash map.
+export type typestore = struct {
+ map: [BUCKETS][]struct {
+ hash: u32,
+ _type: _type,
+ },
+};
+
+// Initializes a new type store.
+export fn store() *typestore = alloc(typestore { ... });
+
+// Retrieves a [[_type]] for a given [[ast::_type]].
+export fn lookup(store: *typestore, t: *ast::_type) const *_type = {
+ const t = fromast(t);
+ const h = hash(&t);
+ let bucket = &store.map[h % BUCKETS];
+ // XXX: Should not have to dereference bucket
+ for (let i = 0z; i < len(*bucket); i += 1) {
+ if (bucket[i].hash == h) {
+ type_finish(&t);
+ return &bucket[i]._type;
+ };
+ };
+ append(*bucket, struct {
+ hash: u32 = h,
+ _type: _type = t,
+ });
+ return &bucket[len(*bucket) - 1]._type;
+};
+
+fn fromast(atype: *ast::_type) _type = {
+ let underlying = match (atype._type) {
+ a: ast::alias_type => {
+ assert(!a.unwrap); // TODO
+ ast::ident_dup(a.ident): alias;
+ },
+ b: ast::builtin_type => b: builtin,
+ * => abort(), // TODO
+ };
+ return _type {
+ flags = atype.flags: flags,
+ _type = underlying,
+ };
+};
+
+fn type_finish(t: *_type) void = {
+ void; // TODO
+};
diff --git a/hare/types/types.ha b/hare/types/types.ha
@@ -0,0 +1,25 @@
+use hare::ast;
+
+// A type alias.
+export type alias = ast::ident;
+
+// A built-in primitive type (int, bool, str, etc).
+export type builtin = enum u8 {
+ // Keep me consistent with ast::builtin
+ BOOL, CHAR, F32, F64, I16, I32, I64, I8, INT, NULL, RUNE, SIZE, STR,
+ U16, U32, U64, U8, UINT, UINTPTR, VOID,
+};
+
+// Flags for a Hare type.
+export type flags = enum u8 {
+ NONE = 0,
+ // Keep me consistent with ast::type_flags
+ CONST = 1 << 0,
+ ERROR = 1 << 1,
+};
+
+// A Hare type.
+export type _type = struct {
+ flags: flags,
+ _type: (alias | builtin),
+};
diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
@@ -355,7 +355,15 @@ hare_ast() {
import.ha \
type.ha \
unit.ha
- gen_ssa hare::ast hare::lex
+ gen_ssa hare::ast hare::lex strings
+}
+
+hare_types() {
+ gen_srcs hare::types \
+ hash.ha \
+ store.ha \
+ types.ha
+ gen_ssa hare::types hare::ast hash hash::fnv endian
}
hare_unparse() {
@@ -733,6 +741,7 @@ hare_ast
hare_lex
hare_module
hare_parse
+hare_types
hare_unparse
hash
hash_adler32
diff --git a/stdlib.mk b/stdlib.mk
@@ -161,6 +161,9 @@ hare_stdlib_deps+=$(stdlib_hare_module)
stdlib_hare_parse=$(HARECACHE)/hare/parse/hare_parse.o
hare_stdlib_deps+=$(stdlib_hare_parse)
+stdlib_hare_types=$(HARECACHE)/hare/types/hare_types.o
+hare_stdlib_deps+=$(stdlib_hare_types)
+
stdlib_hare_unparse=$(HARECACHE)/hare/unparse/hare_unparse.o
hare_stdlib_deps+=$(stdlib_hare_unparse)
@@ -524,7 +527,7 @@ stdlib_hare_ast_srcs= \
$(STDLIB)/hare/ast/type.ha \
$(STDLIB)/hare/ast/unit.ha
-$(HARECACHE)/hare/ast/hare_ast.ssa: $(stdlib_hare_ast_srcs) $(stdlib_rt) $(stdlib_hare_lex)
+$(HARECACHE)/hare/ast/hare_ast.ssa: $(stdlib_hare_ast_srcs) $(stdlib_rt) $(stdlib_hare_lex) $(stdlib_strings)
@printf 'HAREC \t$@\n'
@mkdir -p $(HARECACHE)/hare/ast
@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nhare::ast \
@@ -570,6 +573,18 @@ $(HARECACHE)/hare/parse/hare_parse.ssa: $(stdlib_hare_parse_srcs) $(stdlib_rt) $
@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nhare::parse \
-t$(HARECACHE)/hare/parse/hare_parse.td $(stdlib_hare_parse_srcs)
+# hare::types
+stdlib_hare_types_srcs= \
+ $(STDLIB)/hare/types/hash.ha \
+ $(STDLIB)/hare/types/store.ha \
+ $(STDLIB)/hare/types/types.ha
+
+$(HARECACHE)/hare/types/hare_types.ssa: $(stdlib_hare_types_srcs) $(stdlib_rt) $(stdlib_hare_ast) $(stdlib_hash) $(stdlib_hash_fnv) $(stdlib_endian)
+ @printf 'HAREC \t$@\n'
+ @mkdir -p $(HARECACHE)/hare/types
+ @HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nhare::types \
+ -t$(HARECACHE)/hare/types/hare_types.td $(stdlib_hare_types_srcs)
+
# hare::unparse
stdlib_hare_unparse_srcs= \
$(STDLIB)/hare/unparse/expr.ha \
@@ -1088,6 +1103,9 @@ hare_testlib_deps+=$(testlib_hare_module)
testlib_hare_parse=$(TESTCACHE)/hare/parse/hare_parse.o
hare_testlib_deps+=$(testlib_hare_parse)
+testlib_hare_types=$(TESTCACHE)/hare/types/hare_types.o
+hare_testlib_deps+=$(testlib_hare_types)
+
testlib_hare_unparse=$(TESTCACHE)/hare/unparse/hare_unparse.o
hare_testlib_deps+=$(testlib_hare_unparse)
@@ -1460,7 +1478,7 @@ testlib_hare_ast_srcs= \
$(STDLIB)/hare/ast/type.ha \
$(STDLIB)/hare/ast/unit.ha
-$(TESTCACHE)/hare/ast/hare_ast.ssa: $(testlib_hare_ast_srcs) $(testlib_rt) $(testlib_hare_lex)
+$(TESTCACHE)/hare/ast/hare_ast.ssa: $(testlib_hare_ast_srcs) $(testlib_rt) $(testlib_hare_lex) $(testlib_strings)
@printf 'HAREC \t$@\n'
@mkdir -p $(TESTCACHE)/hare/ast
@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nhare::ast \
@@ -1512,6 +1530,18 @@ $(TESTCACHE)/hare/parse/hare_parse.ssa: $(testlib_hare_parse_srcs) $(testlib_rt)
@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nhare::parse \
-t$(TESTCACHE)/hare/parse/hare_parse.td $(testlib_hare_parse_srcs)
+# hare::types
+testlib_hare_types_srcs= \
+ $(STDLIB)/hare/types/hash.ha \
+ $(STDLIB)/hare/types/store.ha \
+ $(STDLIB)/hare/types/types.ha
+
+$(TESTCACHE)/hare/types/hare_types.ssa: $(testlib_hare_types_srcs) $(testlib_rt) $(testlib_hare_ast) $(testlib_hash) $(testlib_hash_fnv) $(testlib_endian)
+ @printf 'HAREC \t$@\n'
+ @mkdir -p $(TESTCACHE)/hare/types
+ @HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nhare::types \
+ -t$(TESTCACHE)/hare/types/hare_types.td $(testlib_hare_types_srcs)
+
# hare::unparse
testlib_hare_unparse_srcs= \
$(STDLIB)/hare/unparse/expr.ha \
