From 6d15697edce2217a2bbc82def26262d18dac6373 Mon Sep 17 00:00:00 2001 From: Bruce Hill Date: Wed, 21 May 2025 14:25:45 -0400 Subject: Added Set infix operations, as well as Table.with_fallback() and fixed some bugs with update assignment. --- CHANGES.md | 2 ++ api/sets.yaml | 23 ++++++++++++- api/tables.yaml | 25 ++++++++++++++ src/ast.h | 1 + src/compile.c | 16 +++++++-- src/stdlib/tables.c | 94 +++++++++++++++++++++++++++++++++-------------------- src/stdlib/tables.h | 2 ++ src/typecheck.c | 19 +++++++++++ test/sets.tm | 9 +++++ 9 files changed, 153 insertions(+), 38 deletions(-) diff --git a/CHANGES.md b/CHANGES.md index 3e3ac7c9..1b93c338 100644 --- a/CHANGES.md +++ b/CHANGES.md @@ -9,7 +9,9 @@ - Programs can use `--version` as a CLI flag to print a Tomo program's version number and exit. - Added `tomo --prefix` to print the Tomo install prefix. +- Sets now support infix operations for `and`, `or`, `xor`, and `-` - Added Path.sibling() +- Added Table.with_fallback() ## v0.2 diff --git a/api/sets.yaml b/api/sets.yaml index 6bf0d8cc..08111932 100644 --- a/api/sets.yaml +++ b/api/sets.yaml @@ -229,4 +229,25 @@ Set.without: example: | >> |1, 2|.without(|2, 3|) = |1| - + +Table.xor: + short: symmetric difference + description: > + Return set with the elements in one, but not both of the arguments. This is + also known as the symmetric difference or disjunctive union. + return: + type: '|T|' + description: > + A set with the symmetric difference of the arguments. + args: + a: + type: '|T|' + description: > + The first set. + b: + type: '|T|' + description: > + The second set. + example: | + >> |1, 2, 3|.xor(|2, 3, 4|) + = |1, 4| diff --git a/api/tables.yaml b/api/tables.yaml index 6a58e818..f3b648da 100644 --- a/api/tables.yaml +++ b/api/tables.yaml @@ -160,3 +160,28 @@ Table.set: >> t = {"A"=1, "B"=2, "C"=3} +Table.with_fallback: + short: return a table with a new fallback + description: > + Return a copy of a table with a different fallback table. + return: + type: '{K=V}' + description: > + The original table with a different fallback. + args: + t: + type: '{K=V}' + description: > + The table whose fallback will be replaced. + fallback: + type: '{K=V}?' + description: > + The new fallback table value. + example: | + t := {"A"=1; fallback={"B"=2}} + t2 = t.with_fallback({"B"=3"}) + >> t2["B"] + = 3? + t3 = t.with_fallback(none) + >> t2["B"] + = none diff --git a/src/ast.h b/src/ast.h index 47ff3caf..486b5818 100644 --- a/src/ast.h +++ b/src/ast.h @@ -23,6 +23,7 @@ #define Match(x, _tag) ((x)->tag == _tag ? &(x)->__data._tag : (errx(1, __FILE__ ":%d This was supposed to be a " # _tag "\n", __LINE__), &(x)->__data._tag)) #define DeclareMatch(var, x, _tag) __typeof((x)->__data._tag) *var = Match(x, _tag) #define BINARY_OPERANDS(ast) ({ if (!is_binary_operation(ast)) errx(1, __FILE__ ":%d This is not a binary operation!", __LINE__); (ast)->__data.Plus; }) +#define UPDATE_OPERANDS(ast) ({ if (!is_update_assignment(ast)) errx(1, __FILE__ ":%d This is not an update assignment!", __LINE__); (ast)->__data.PlusUpdate; }) #define REVERSE_LIST(list) do { \ __typeof(list) _prev = NULL; \ diff --git a/src/compile.c b/src/compile.c index 2ecb8c9e..bd963951 100644 --- a/src/compile.c +++ b/src/compile.c @@ -505,7 +505,7 @@ static CORD compile_update_assignment(env_t *env, ast_t *ast) if (!is_update_assignment(ast)) code_err(ast, "This is not an update assignment"); - binary_operands_t update = BINARY_OPERANDS(ast); + binary_operands_t update = UPDATE_OPERANDS(ast); type_t *lhs_t = get_type(env, update.lhs); @@ -696,6 +696,8 @@ static CORD compile_binary_op(env_t *env, ast_t *ast) return CORD_all("(", lhs, " + ", rhs, ")"); } case Minus: { + if (overall_t->tag == SetType) + return CORD_all("Table$without(", lhs, ", ", rhs, ", ", compile_type_info(overall_t), ")"); if (overall_t->tag != IntType && overall_t->tag != NumType && overall_t->tag != ByteType) code_err(ast, "Math operations are only supported for values of the same numeric type, not ", type_to_str(lhs_t), " and ", type_to_str(rhs_t)); return CORD_all("(", lhs, " - ", rhs, ")"); @@ -725,6 +727,8 @@ static CORD compile_binary_op(env_t *env, ast_t *ast) return CORD_all("(", lhs, " && ", rhs, ")"); else if (overall_t->tag == IntType || overall_t->tag == ByteType) return CORD_all("(", lhs, " & ", rhs, ")"); + else if (overall_t->tag == SetType) + return CORD_all("Table$overlap(", lhs, ", ", rhs, ", ", compile_type_info(overall_t), ")"); else code_err(ast, "The 'and' operator isn't supported between ", type_to_str(lhs_t), " and ", type_to_str(rhs_t), " values"); } @@ -736,6 +740,8 @@ static CORD compile_binary_op(env_t *env, ast_t *ast) return CORD_all("(", lhs, " || ", rhs, ")"); } else if (overall_t->tag == IntType || overall_t->tag == ByteType) { return CORD_all("(", lhs, " | ", rhs, ")"); + } else if (overall_t->tag == SetType) { + return CORD_all("Table$with(", lhs, ", ", rhs, ", ", compile_type_info(overall_t), ")"); } else { code_err(ast, "The 'or' operator isn't supported between ", type_to_str(lhs_t), " and ", type_to_str(rhs_t), " values"); } @@ -744,6 +750,8 @@ static CORD compile_binary_op(env_t *env, ast_t *ast) // TODO: support optional values in `xor` expressions if (overall_t->tag == BoolType || overall_t->tag == IntType || overall_t->tag == ByteType) return CORD_all("(", lhs, " ^ ", rhs, ")"); + else if (overall_t->tag == SetType) + return CORD_all("Table$xor(", lhs, ", ", rhs, ", ", compile_type_info(overall_t), ")"); else code_err(ast, "The 'xor' operator isn't supported between ", type_to_str(lhs_t), " and ", type_to_str(rhs_t), " values"); } @@ -1204,7 +1212,7 @@ static CORD _compile_statement(env_t *env, ast_t *ast) test_code = CORD_all(test_code, "$1; })"); } } else if (is_update_assignment(test->expr)) { - binary_operands_t update = BINARY_OPERANDS(test->expr); + binary_operands_t update = UPDATE_OPERANDS(test->expr); type_t *lhs_t = get_type(env, update.lhs); if (update.lhs->tag == Index) { type_t *indexed = value_type(get_type(env, Match(update.lhs, Index)->indexed)); @@ -3428,6 +3436,10 @@ CORD compile(env_t *env, ast_t *ast) self = compile_to_pointer_depth(env, call->self, 0, false); (void)compile_arguments(env, ast, NULL, call->args); return CORD_all("Table$sorted(", self, ", ", compile_type_info(self_value_t), ")"); + } else if (streq(call->name, "with_fallback")) { + self = compile_to_pointer_depth(env, call->self, 0, false); + arg_t *arg_spec = new(arg_t, .name="fallback", .type=Type(OptionalType, self_value_t)); + return CORD_all("Table$with_fallback(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); } else code_err(ast, "There is no '", call->name, "' method for tables"); } default: { diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c index 8e3afe45..762afb06 100644 --- a/src/stdlib/tables.c +++ b/src/stdlib/tables.c @@ -640,19 +640,15 @@ public Table_t Table$overlap(Table_t a, Table_t b, const TypeInfo_t *type) // Return a table such that t[k]==a[k] for all k such that a.has(k), b.has(k), and a[k]==b[k] Table_t result = {}; const size_t offset = value_offset(type); - for (int64_t i = 0; i < Table$length(a); i++) { - void *key = GET_ENTRY(a, i); - void *a_value = key + offset; - void *b_value = Table$get(b, key, type); - if (b_value && generic_equal(a_value, b_value, type->TableInfo.value)) - Table$set(&result, key, a_value, type); - } - - if (a.fallback) { - result.fallback = new(Table_t); - *result.fallback = Table$overlap(*a.fallback, b, type); + for (Table_t *t = &a; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + void *a_value = key + offset; + void *b_value = Table$get(b, key, type); + if (b_value && generic_equal(a_value, b_value, type->TableInfo.value)) + Table$set(&result, key, a_value, type); + } } - return result; } @@ -662,22 +658,41 @@ public Table_t Table$with(Table_t a, Table_t b, const TypeInfo_t *type) // return a table such that t[k]==b[k] for all k such that b.has(k), and t[k]==a[k] for all k such that a.has(k) and not b.has(k) Table_t result = {}; const size_t offset = value_offset(type); - for (int64_t i = 0; i < Table$length(a); i++) { - void *key = GET_ENTRY(a, i); - Table$set(&result, key, key + offset, type); + for (Table_t *t = &a; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + Table$set(&result, key, key + offset, type); + } } - for (int64_t i = 0; i < Table$length(b); i++) { - void *key = GET_ENTRY(b, i); - Table$set(&result, key, key + offset, type); + for (Table_t *t = &b; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + Table$set(&result, key, key + offset, type); + } } + return result; +} - if (a.fallback && b.fallback) { - result.fallback = new(Table_t); - *result.fallback = Table$with(*a.fallback, *b.fallback, type); - } else { - result.fallback = a.fallback ? a.fallback : b.fallback; +// Xor is "disjunctive union" or "symmetric difference" in formal terms +public Table_t Table$xor(Table_t a, Table_t b, const TypeInfo_t *type) +{ + // return a table with elements in `a` or `b`, but not both + Table_t result = {}; + const size_t offset = value_offset(type); + for (Table_t *t = &a; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + if (Table$get(b, key, type) == NULL) + Table$set(&result, key, key + offset, type); + } + } + for (Table_t *t = &b; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + if (Table$get(a, key, type) == NULL) + Table$set(&result, key, key + offset, type); + } } - return result; } @@ -687,20 +702,29 @@ public Table_t Table$without(Table_t a, Table_t b, const TypeInfo_t *type) // Return a table such that t[k]==a[k] for all k such that not b.has(k) or b[k] != a[k] Table_t result = {}; const size_t offset = value_offset(type); - for (int64_t i = 0; i < Table$length(a); i++) { - void *key = GET_ENTRY(a, i); - void *a_value = key + offset; - void *b_value = Table$get(b, key, type); - if (!b_value || !generic_equal(a_value, b_value, type->TableInfo.value)) - Table$set(&result, key, a_value, type); + for (Table_t *t = &a; t; t = t->fallback) { + for (int64_t i = 0; i < Table$length(*t); i++) { + void *key = GET_ENTRY(*t, i); + void *a_value = key + offset; + void *b_value = Table$get(b, key, type); + if (!b_value || !generic_equal(a_value, b_value, type->TableInfo.value)) + Table$set(&result, key, a_value, type); + } } + return result; +} - if (a.fallback) { - result.fallback = new(Table_t); - *result.fallback = Table$without(*a.fallback, b, type); +public Table_t Table$with_fallback(Table_t t, OptionalTable_t fallback) +{ + if (fallback.entries.length <= 0) { + t.fallback = NULL; + return t; + } else { + TABLE_INCREF(fallback); + t.fallback = GC_MALLOC(sizeof(Table_t)); + *t.fallback = fallback; + return t; } - - return result; } PUREFUNC public bool Table$is_subset_of(Table_t a, Table_t b, bool strict, const TypeInfo_t *type) diff --git a/src/stdlib/tables.h b/src/stdlib/tables.h index ad6127c7..f80c16c3 100644 --- a/src/stdlib/tables.h +++ b/src/stdlib/tables.h @@ -59,6 +59,8 @@ void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type); Table_t Table$overlap(Table_t a, Table_t b, const TypeInfo_t *type); Table_t Table$with(Table_t a, Table_t b, const TypeInfo_t *type); Table_t Table$without(Table_t a, Table_t b, const TypeInfo_t *type); +Table_t Table$xor(Table_t a, Table_t b, const TypeInfo_t *type); +Table_t Table$with_fallback(Table_t t, OptionalTable_t fallback); PUREFUNC bool Table$is_subset_of(Table_t a, Table_t b, bool strict, const TypeInfo_t *type); PUREFUNC bool Table$is_superset_of(Table_t a, Table_t b, bool strict, const TypeInfo_t *type); diff --git a/src/typecheck.c b/src/typecheck.c index f97235b4..b98cb84b 100644 --- a/src/typecheck.c +++ b/src/typecheck.c @@ -956,6 +956,7 @@ type_t *get_type(env_t *env, ast_t *ast) else if (streq(call->name, "remove")) return Type(VoidType); else if (streq(call->name, "set")) return Type(VoidType); else if (streq(call->name, "sorted")) return self_value_t; + else if (streq(call->name, "with_fallback")) return self_value_t; code_err(ast, "There is no '", call->name, "' method for ", type_to_str(self_value_t), " tables"); } default: { @@ -1069,6 +1070,10 @@ type_t *get_type(env_t *env, ast_t *ast) type_t *lhs_t = get_type(env, binop.lhs); type_t *rhs_t = get_type(env, binop.rhs); + type_t *lhs_val = value_type(lhs_t), *rhs_val = value_type(rhs_t); + if (type_eq(lhs_val, rhs_val) && lhs_val->tag == SetType) + return lhs_val; + if (binop.lhs->tag == Int && is_int_type(rhs_t)) return rhs_t; else if (binop.rhs->tag == Int && is_int_type(lhs_t)) @@ -1115,6 +1120,10 @@ type_t *get_type(env_t *env, ast_t *ast) type_t *lhs_t = get_type(env, binop.lhs); type_t *rhs_t = get_type(env, binop.rhs); + type_t *lhs_val = value_type(lhs_t), *rhs_val = value_type(rhs_t); + if (type_eq(lhs_val, rhs_val) && lhs_val->tag == SetType) + return lhs_val; + if (binop.lhs->tag == Int && is_int_type(rhs_t)) return rhs_t; else if (binop.rhs->tag == Int && is_int_type(lhs_t)) @@ -1149,6 +1158,10 @@ type_t *get_type(env_t *env, ast_t *ast) type_t *lhs_t = get_type(env, binop.lhs); type_t *rhs_t = get_type(env, binop.rhs); + type_t *lhs_val = value_type(lhs_t), *rhs_val = value_type(rhs_t); + if (type_eq(lhs_val, rhs_val) && lhs_val->tag == SetType) + return lhs_val; + if (binop.lhs->tag == Int && is_int_type(rhs_t)) return rhs_t; else if (binop.rhs->tag == Int && is_int_type(lhs_t)) @@ -1198,6 +1211,12 @@ type_t *get_type(env_t *env, ast_t *ast) type_t *lhs_t = get_type(env, binop.lhs); type_t *rhs_t = get_type(env, binop.rhs); + if (ast->tag == Minus) { + type_t *lhs_val = value_type(lhs_t), *rhs_val = value_type(rhs_t); + if (type_eq(lhs_val, rhs_val) && lhs_val->tag == SetType) + return lhs_val; + } + if (ast->tag == LeftShift || ast->tag == UnsignedLeftShift || ast->tag == RightShift || ast->tag == UnsignedRightShift) { if (!is_int_type(rhs_t)) code_err(binop.rhs, "I only know how to do bit shifting by integer amounts, not ", type_to_str(rhs_t)); diff --git a/test/sets.tm b/test/sets.tm index fe2e91f8..85e53463 100644 --- a/test/sets.tm +++ b/test/sets.tm @@ -40,3 +40,12 @@ func main() >> empty : |Int| = || = || + + >> |1,2,3| or |3,4| + = |1,2,3,4| + >> |1,2,3| and |3,4| + = |3| + >> |1,2,3| xor |3,4| + = |1,2,4| + >> |1,2,3| - |3,4| + >> |1,2| -- cgit v1.2.3