From 44cd26f2cebd760a53aa4ff1b7779e718a101650 Mon Sep 17 00:00:00 2001 From: Bruce Hill Date: Sun, 6 Apr 2025 22:45:02 -0400 Subject: Rename Array -> List in all code and docs --- src/ast.c | 4 +- src/ast.h | 8 +- src/compile.c | 268 ++++++++-------- src/environment.c | 38 +-- src/environment.h | 2 +- src/parse.c | 22 +- src/repl.c | 38 +-- src/stdlib/README.md | 2 +- src/stdlib/arrays.c | 813 ----------------------------------------------- src/stdlib/arrays.h | 137 -------- src/stdlib/c_strings.c | 2 +- src/stdlib/datatypes.h | 36 +-- src/stdlib/enums.c | 4 +- src/stdlib/enums.h | 2 +- src/stdlib/integers.c | 16 +- src/stdlib/integers.h | 6 +- src/stdlib/lists.c | 813 +++++++++++++++++++++++++++++++++++++++++++++++ src/stdlib/lists.h | 137 ++++++++ src/stdlib/metamethods.c | 16 +- src/stdlib/metamethods.h | 8 +- src/stdlib/nums.c | 2 +- src/stdlib/optionals.c | 6 +- src/stdlib/optionals.h | 4 +- src/stdlib/paths.c | 102 +++--- src/stdlib/paths.h | 18 +- src/stdlib/pointers.c | 4 +- src/stdlib/pointers.h | 2 +- src/stdlib/stdlib.c | 26 +- src/stdlib/structs.c | 4 +- src/stdlib/structs.h | 2 +- src/stdlib/tables.c | 24 +- src/stdlib/tables.h | 12 +- src/stdlib/text.c | 96 +++--- src/stdlib/text.h | 24 +- src/stdlib/tomo.h | 2 +- src/stdlib/types.c | 2 +- src/stdlib/types.h | 6 +- src/tomo.c | 50 +-- src/typecheck.c | 68 ++-- src/types.c | 38 +-- src/types.h | 4 +- 41 files changed, 1434 insertions(+), 1434 deletions(-) delete mode 100644 src/stdlib/arrays.c delete mode 100644 src/stdlib/arrays.h create mode 100644 src/stdlib/lists.c create mode 100644 src/stdlib/lists.h (limited to 'src') diff --git a/src/ast.c b/src/ast.c index b3506058..2d564d98 100644 --- a/src/ast.c +++ b/src/ast.c @@ -149,7 +149,7 @@ CORD ast_to_xml(ast_t *ast) T(StackReference, "%r", ast_to_xml(data.value)) T(Min, "%r%r%r", ast_to_xml(data.lhs), ast_to_xml(data.rhs), optional_tagged("key", data.key)) T(Max, "%r%r%r", ast_to_xml(data.lhs), ast_to_xml(data.rhs), optional_tagged("key", data.key)) - T(Array, "%r", ast_list_to_xml(data.items)) + T(List, "%r", ast_list_to_xml(data.items)) T(Set, "%r", ast_list_to_xml(data.items)) T(Table, "%r%r
", optional_tagged("default-value", data.default_value), @@ -224,7 +224,7 @@ CORD type_ast_to_xml(type_ast_t *t) T(VarTypeAST, "%s", data.name) T(PointerTypeAST, "%r", data.is_stack ? "yes" : "no", type_ast_to_xml(data.pointed)) - T(ArrayTypeAST, "%r", type_ast_to_xml(data.item)) + T(ListTypeAST, "%r", type_ast_to_xml(data.item)) T(SetTypeAST, "%r", type_ast_to_xml(data.item)) T(TableTypeAST, "%r %r", type_ast_to_xml(data.key), type_ast_to_xml(data.value)) T(FunctionTypeAST, "%r %r", arg_list_to_xml(data.args), type_ast_to_xml(data.ret)) diff --git a/src/ast.h b/src/ast.h index aeb418d9..441fde81 100644 --- a/src/ast.h +++ b/src/ast.h @@ -64,7 +64,7 @@ typedef enum { UnknownTypeAST, VarTypeAST, PointerTypeAST, - ArrayTypeAST, + ListTypeAST, SetTypeAST, TableTypeAST, FunctionTypeAST, @@ -93,7 +93,7 @@ struct type_ast_s { } PointerTypeAST; struct { type_ast_t *item; - } ArrayTypeAST; + } ListTypeAST; struct { type_ast_t *key, *value; ast_t *default_value; @@ -134,7 +134,7 @@ typedef enum { RightShiftUpdate, UnsignedRightShiftUpdate, AndUpdate, OrUpdate, XorUpdate, Not, Negative, HeapAllocate, StackReference, Min, Max, - Array, Set, Table, TableEntry, Comprehension, + List, Set, Table, TableEntry, Comprehension, FunctionDef, Lambda, ConvertDef, FunctionCall, MethodCall, Block, @@ -204,7 +204,7 @@ struct ast_s { } Min, Max; struct { ast_list_t *items; - } Array; + } List; struct { ast_list_t *items; } Set; diff --git a/src/compile.c b/src/compile.c index cdfaf5c6..6cb25de0 100644 --- a/src/compile.c +++ b/src/compile.c @@ -34,14 +34,14 @@ static CORD compile_none(type_t *t); static CORD compile_empty(type_t *t); static CORD compile_declared_value(env_t *env, ast_t *declaration_ast); static CORD compile_to_type(env_t *env, ast_t *ast, type_t *t); -static CORD compile_typed_array(env_t *env, ast_t *ast, type_t *array_type); +static CORD compile_typed_list(env_t *env, ast_t *ast, type_t *list_type); static CORD compile_typed_set(env_t *env, ast_t *ast, type_t *set_type); static CORD compile_typed_table(env_t *env, ast_t *ast, type_t *table_type); static CORD compile_typed_allocation(env_t *env, ast_t *ast, type_t *pointer_type); static CORD check_none(type_t *t, CORD value); static CORD optional_into_nonnone(type_t *t, CORD value); static CORD compile_string_literal(CORD literal); -static ast_t *add_to_array_comprehension(ast_t *item, ast_t *subject); +static ast_t *add_to_list_comprehension(ast_t *item, ast_t *subject); static ast_t *add_to_table_comprehension(ast_t *entry, ast_t *subject); static ast_t *add_to_set_comprehension(ast_t *item, ast_t *subject); static CORD compile_lvalue(env_t *env, ast_t *ast); @@ -174,9 +174,9 @@ static bool promote(env_t *env, ast_t *ast, CORD *code, type_t *actual, type_t * return true; } - // Set -> Array promotion: - if (needed->tag == ArrayType && actual->tag == SetType - && type_eq(Match(needed, ArrayType)->item_type, Match(actual, SetType)->item_type)) { + // Set -> List promotion: + if (needed->tag == ListType && actual->tag == SetType + && type_eq(Match(needed, ListType)->item_type, Match(actual, SetType)->item_type)) { *code = CORD_all("(", *code, ").entries"); return true; } @@ -187,8 +187,8 @@ static bool promote(env_t *env, ast_t *ast, CORD *code, type_t *actual, type_t * CORD compile_maybe_incref(env_t *env, ast_t *ast, type_t *t) { if (is_idempotent(ast) && can_be_mutated(env, ast)) { - if (t->tag == ArrayType) - return CORD_all("ARRAY_COPY(", compile_to_type(env, ast, t), ")"); + if (t->tag == ListType) + return CORD_all("LIST_COPY(", compile_to_type(env, ast, t), ")"); else if (t->tag == TableType || t->tag == SetType) return CORD_all("TABLE_COPY(", compile_to_type(env, ast, t), ")"); } @@ -253,8 +253,8 @@ static void add_closed_vars(Table_t *closed_vars, env_t *enclosing_scope, env_t add_closed_vars(closed_vars, enclosing_scope, env, Match(ast, Max)->key); break; } - case Array: { - for (ast_list_t *item = Match(ast, Array)->items; item; item = item->next) + case List: { + for (ast_list_t *item = Match(ast, List)->items; item; item = item->next) add_closed_vars(closed_vars, enclosing_scope, env, item->ast); break; } @@ -283,7 +283,7 @@ static void add_closed_vars(Table_t *closed_vars, env_t *enclosing_scope, env_t return add_closed_vars(closed_vars, enclosing_scope, env, loop); } - // Array/Set/Table comprehension: + // List/Set/Table comprehension: ast_t *body = comp->expr; if (comp->filter) body = WrapAST(comp->expr, If, .condition=comp->filter, .body=body); @@ -746,8 +746,8 @@ static CORD compile_binary_op(env_t *env, ast_t *ast) case TextType: { return CORD_all("Text$concat(", lhs, ", ", rhs, ")"); } - case ArrayType: { - return CORD_all("Array$concat(", lhs, ", ", rhs, ", sizeof(", compile_type(Match(overall_t, ArrayType)->item_type), "))"); + case ListType: { + return CORD_all("List$concat(", lhs, ", ", rhs, ", sizeof(", compile_type(Match(overall_t, ListType)->item_type), "))"); } default: code_err(ast, "Concatenation isn't supported between ", type_to_str(lhs_t), " and ", type_to_str(rhs_t), " values"); @@ -793,7 +793,7 @@ CORD compile_type(type_t *t) else return CORD_all(namespace_prefix(text->env, text->env->namespace->parent), text->lang, "$$type"); } - case ArrayType: return "Array_t"; + case ListType: return "List_t"; case SetType: return "Table_t"; case TableType: return "Table_t"; case FunctionType: { @@ -827,7 +827,7 @@ CORD compile_type(type_t *t) case TextType: return Match(nonnull, TextType)->lang ? compile_type(nonnull) : "OptionalText_t"; case IntType: case BigIntType: case NumType: case BoolType: case ByteType: - case ArrayType: case TableType: case SetType: + case ListType: case TableType: case SetType: return CORD_all("Optional", compile_type(nonnull)); case StructType: { if (nonnull == PATH_TYPE) @@ -872,19 +872,19 @@ CORD compile_lvalue(env_t *env, ast_t *ast) container_t = value_type(container_t); type_t *index_t = get_type(env, index->index); - if (container_t->tag == ArrayType) { + if (container_t->tag == ListType) { CORD target_code = compile_to_pointer_depth(env, index->indexed, 1, false); - type_t *item_type = Match(container_t, ArrayType)->item_type; + type_t *item_type = Match(container_t, ListType)->item_type; CORD index_code = index->index->tag == Int ? compile_int_to_type(env, index->index, Type(IntType, .bits=TYPE_IBITS64)) : (index_t->tag == BigIntType ? CORD_all("Int64$from_int(", compile(env, index->index), ", no)") : CORD_all("(Int64_t)(", compile(env, index->index), ")")); if (index->unchecked) { - return CORD_all("Array_lvalue_unchecked(", compile_type(item_type), ", ", target_code, ", ", + return CORD_all("List_lvalue_unchecked(", compile_type(item_type), ", ", target_code, ", ", index_code, ", sizeof(", compile_type(item_type), "))"); } else { - return CORD_all("Array_lvalue(", compile_type(item_type), ", ", target_code, ", ", + return CORD_all("List_lvalue(", compile_type(item_type), ", ", target_code, ", ", index_code, ", ", String((int)(ast->start - ast->file->text)), ", ", String((int)(ast->end - ast->file->text)), ")"); @@ -975,7 +975,7 @@ CORD check_none(type_t *t, CORD value) return CORD_all("({(", value, ").fn == NULL;})"); else if (t->tag == NumType) return CORD_all("isnan(", value, ")"); - else if (t->tag == ArrayType) + else if (t->tag == ListType) return CORD_all("({(", value, ").length < 0;})"); else if (t->tag == TableType || t->tag == SetType) return CORD_all("({(", value, ").entries.length < 0;})"); @@ -997,7 +997,7 @@ static CORD compile_condition(env_t *env, ast_t *ast) return compile(env, ast); } else if (t->tag == TextType) { return CORD_all("(", compile(env, ast), ").length"); - } else if (t->tag == ArrayType) { + } else if (t->tag == ListType) { return CORD_all("(", compile(env, ast), ").length"); } else if (t->tag == TableType || t->tag == SetType) { return CORD_all("(", compile(env, ast), ").entries.length"); @@ -1462,7 +1462,7 @@ static CORD _compile_statement(env_t *env, ast_t *ast) auto for_ = Match(ast, For); // If we're iterating over a comprehension, that's actually just doing - // one loop, we don't need to compile the comprehension as an array + // one loop, we don't need to compile the comprehension as a list // comprehension. This is a common case for reducers like `(+: i*2 for i in 5)` // or `(and) x.is_good() for x in xs` if (for_->iter->tag == Comprehension) { @@ -1565,8 +1565,8 @@ static CORD _compile_statement(env_t *env, ast_t *ast) type_t *iter_value_t = value_type(iter_t); switch (iter_value_t->tag) { - case ArrayType: { - type_t *item_t = Match(iter_value_t, ArrayType)->item_type; + case ListType: { + type_t *item_t = Match(iter_value_t, ListType)->item_type; CORD index = CORD_EMPTY; CORD value = CORD_EMPTY; if (for_->vars) { @@ -1601,17 +1601,17 @@ static CORD _compile_statement(env_t *env, ast_t *ast) if (iter_t->tag == PointerType) { loop = CORD_all("{\n" - "Array_t *ptr = ", compile_to_pointer_depth(env, for_->iter, 1, false), ";\n" - "\nARRAY_INCREF(*ptr);\n" - "Array_t iterating = *ptr;\n", + "List_t *ptr = ", compile_to_pointer_depth(env, for_->iter, 1, false), ";\n" + "\nLIST_INCREF(*ptr);\n" + "List_t iterating = *ptr;\n", loop, stop, - "\nARRAY_DECREF(*ptr);\n" + "\nLIST_DECREF(*ptr);\n" "}\n"); } else { loop = CORD_all("{\n" - "Array_t iterating = ", compile_to_pointer_depth(env, for_->iter, 0, false), ";\n", + "List_t iterating = ", compile_to_pointer_depth(env, for_->iter, 0, false), ";\n", loop, stop, "}\n"); @@ -1657,15 +1657,15 @@ static CORD _compile_statement(env_t *env, ast_t *ast) loop = CORD_all( "{\n", "Table_t *t = ", compile_to_pointer_depth(env, for_->iter, 1, false), ";\n" - "ARRAY_INCREF(t->entries);\n" - "Array_t iterating = t->entries;\n", + "LIST_INCREF(t->entries);\n" + "List_t iterating = t->entries;\n", loop, - "ARRAY_DECREF(t->entries);\n" + "LIST_DECREF(t->entries);\n" "}\n"); } else { loop = CORD_all( "{\n", - "Array_t iterating = (", compile_to_pointer_depth(env, for_->iter, 0, false), ").entries;\n", + "List_t iterating = (", compile_to_pointer_depth(env, for_->iter, 0, false), ").entries;\n", loop, "}\n"); } @@ -1834,7 +1834,7 @@ static CORD _compile_statement(env_t *env, ast_t *ast) return compile_statement(env, loop); } - // Array/Set/Table comprehension: + // List/Set/Table comprehension: comprehension_body_t get_body = (void*)env->comprehension_action->fn; ast_t *body = get_body(comp->expr, env->comprehension_action->userdata); if (comp->filter) @@ -1911,7 +1911,7 @@ CORD expr_as_text(CORD expr, type_t *t, CORD color) return CORD_asprintf("%r$as_text(stack(%r), %r, &%r$info)", name, expr, color, name); } case TextType: return CORD_asprintf("Text$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); - case ArrayType: return CORD_asprintf("Array$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); + case ListType: return CORD_asprintf("List$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); case SetType: return CORD_asprintf("Table$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); case TableType: return CORD_asprintf("Table$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); case FunctionType: case ClosureType: return CORD_asprintf("Func$as_text(stack(%r), %r, %r)", expr, color, compile_type_info(t)); @@ -1964,8 +1964,8 @@ CORD compile_to_pointer_depth(env_t *env, ast_t *ast, int64_t target_depth, bool t = ptr->pointed; } - if (needs_incref && t->tag == ArrayType) - val = CORD_all("ARRAY_COPY(", val, ")"); + if (needs_incref && t->tag == ListType) + val = CORD_all("LIST_COPY(", val, ")"); else if (needs_incref && (t->tag == TableType || t->tag == SetType)) val = CORD_all("TABLE_COPY(", val, ")"); @@ -1991,8 +1991,8 @@ CORD compile_to_type(env_t *env, ast_t *ast, type_t *t) return compile_none(t); } else if (t->tag == PointerType && (ast->tag == HeapAllocate || ast->tag == StackReference)) { return compile_typed_allocation(env, ast, t); - } else if (t->tag == ArrayType && ast->tag == Array) { - return compile_typed_array(env, ast, t); + } else if (t->tag == ListType && ast->tag == List) { + return compile_typed_list(env, ast, t); } else if (t->tag == TableType && ast->tag == Table) { return compile_typed_table(env, ast, t); } else if (t->tag == SetType && ast->tag == Set) { @@ -2015,7 +2015,7 @@ CORD compile_to_type(env_t *env, ast_t *ast, type_t *t) type_t *self_type = get_type(env, methodcall->self); // Currently, this is only implemented for cases where you have the return type // and the self type equal to each other, because that's the main case I care - // about with array and set methods (e.g. `Array.sorted()`) + // about with list and set methods (e.g. `List.sorted()`) if (is_incomplete_type(self_type) && type_eq(self_type, actual)) { type_t *completed_self = most_complete_type(self_type, t); if (completed_self) { @@ -2037,48 +2037,48 @@ CORD compile_to_type(env_t *env, ast_t *ast, type_t *t) return code; } -CORD compile_typed_array(env_t *env, ast_t *ast, type_t *array_type) +CORD compile_typed_list(env_t *env, ast_t *ast, type_t *list_type) { - auto array = Match(ast, Array); - if (!array->items) - return "(Array_t){.length=0}"; + auto list = Match(ast, List); + if (!list->items) + return "(List_t){.length=0}"; - type_t *item_type = Match(array_type, ArrayType)->item_type; + type_t *item_type = Match(list_type, ListType)->item_type; int64_t n = 0; - for (ast_list_t *item = array->items; item; item = item->next) { + for (ast_list_t *item = list->items; item; item = item->next) { ++n; if (item->ast->tag == Comprehension) - goto array_comprehension; + goto list_comprehension; } { env_t *scope = item_type->tag == EnumType ? with_enum_scope(env, item_type) : env; if (is_incomplete_type(item_type)) - code_err(ast, "This array's type can't be inferred!"); - CORD code = CORD_all("TypedArrayN(", compile_type(item_type), CORD_asprintf(", %ld", n)); - for (ast_list_t *item = array->items; item; item = item->next) { + code_err(ast, "This list's type can't be inferred!"); + CORD code = CORD_all("TypedListN(", compile_type(item_type), CORD_asprintf(", %ld", n)); + for (ast_list_t *item = list->items; item; item = item->next) { code = CORD_all(code, ", ", compile_to_type(scope, item->ast, item_type)); } return CORD_cat(code, ")"); } - array_comprehension: + list_comprehension: { env_t *scope = item_type->tag == EnumType ? with_enum_scope(env, item_type) : fresh_scope(env); static int64_t comp_num = 1; - const char *comprehension_name = String("arr$", comp_num++); + const char *comprehension_name = String("list$", comp_num++); ast_t *comprehension_var = LiteralCode(CORD_all("&", comprehension_name), - .type=Type(PointerType, .pointed=array_type, .is_stack=true)); - Closure_t comp_action = {.fn=add_to_array_comprehension, .userdata=comprehension_var}; + .type=Type(PointerType, .pointed=list_type, .is_stack=true)); + Closure_t comp_action = {.fn=add_to_list_comprehension, .userdata=comprehension_var}; scope->comprehension_action = &comp_action; - CORD code = CORD_all("({ Array_t ", comprehension_name, " = {};"); - // set_binding(scope, comprehension_name, array_type, comprehension_name); - for (ast_list_t *item = array->items; item; item = item->next) { + CORD code = CORD_all("({ List_t ", comprehension_name, " = {};"); + // set_binding(scope, comprehension_name, list_type, comprehension_name); + for (ast_list_t *item = list->items; item; item = item->next) { if (item->ast->tag == Comprehension) code = CORD_all(code, "\n", compile_statement(scope, item->ast)); else - code = CORD_all(code, compile_statement(env, add_to_array_comprehension(item->ast, comprehension_var))); + code = CORD_all(code, compile_statement(env, add_to_list_comprehension(item->ast, comprehension_var))); } code = CORD_all(code, " ", comprehension_name, "; })"); return code; @@ -2463,7 +2463,7 @@ CORD compile_none(type_t *t) } case BoolType: return "NONE_BOOL"; case ByteType: return "NONE_BYTE"; - case ArrayType: return "NONE_ARRAY"; + case ListType: return "NONE_LIST"; case TableType: return "NONE_TABLE"; case SetType: return "NONE_TABLE"; case TextType: return "NONE_TEXT"; @@ -2505,7 +2505,7 @@ CORD compile_empty(type_t *t) } case ByteType: return "((Byte_t)0)"; case BoolType: return "((Bool_t)no)"; - case ArrayType: return "((Array_t){})"; + case ListType: return "((List_t){})"; case TableType: case SetType: return "((Table_t){})"; case TextType: return "Text(\"\")"; case CStringType: return "\"\""; @@ -2577,7 +2577,7 @@ ast_t *add_to_table_comprehension(ast_t *entry, ast_t *subject) .args=new(arg_ast_t, .value=e->key, .next=new(arg_ast_t, .value=e->value))); } -ast_t *add_to_array_comprehension(ast_t *item, ast_t *subject) +ast_t *add_to_list_comprehension(ast_t *item, ast_t *subject) { return WrapAST(item, MethodCall, .name="insert", .self=subject, .args=new(arg_ast_t, .value=item)); } @@ -2634,7 +2634,7 @@ CORD compile(env_t *env, ast_t *ast) return CORD_all("!(", compile(env, value), ")"); else if (t->tag == IntType || t->tag == ByteType) return CORD_all("~(", compile(env, value), ")"); - else if (t->tag == ArrayType) + else if (t->tag == ListType) return CORD_all("((", compile(env, value), ").length == 0)"); else if (t->tag == SetType || t->tag == TableType) return CORD_all("((", compile(env, value), ").entries.length == 0)"); @@ -2884,13 +2884,13 @@ CORD compile(env_t *env, ast_t *ast) comparison, " ? ternary$lhs : ternary$rhs;\n" "})"); } - case Array: { - auto array = Match(ast, Array); - if (!array->items) - return "(Array_t){.length=0}"; + case List: { + auto list = Match(ast, List); + if (!list->items) + return "(List_t){.length=0}"; - type_t *array_type = get_type(env, ast); - return compile_typed_array(env, ast, array_type); + type_t *list_type = get_type(env, ast); + return compile_typed_list(env, ast, list_type); } case Table: { auto table = Match(ast, Table); @@ -2919,7 +2919,7 @@ CORD compile(env_t *env, ast_t *ast) if (base->tag == TableEntry) return compile(env, WrapAST(ast, Table, .entries=new(ast_list_t, .ast=ast))); else - return compile(env, WrapAST(ast, Array, .items=new(ast_list_t, .ast=ast))); + return compile(env, WrapAST(ast, List, .items=new(ast_list_t, .ast=ast))); } case Lambda: { auto lambda = Match(ast, Lambda); @@ -2989,8 +2989,8 @@ CORD compile(env_t *env, ast_t *ast) binding_t *b = get_binding(env, entry->name); assert(b); CORD binding_code = b->code; - if (entry->b->type->tag == ArrayType) - userdata = CORD_all(userdata, ", ARRAY_COPY(", binding_code, ")"); + if (entry->b->type->tag == ListType) + userdata = CORD_all(userdata, ", LIST_COPY(", binding_code, ")"); else if (entry->b->type->tag == TableType || entry->b->type->tag == SetType) userdata = CORD_all(userdata, ", TABLE_COPY(", binding_code, ")"); else @@ -3049,66 +3049,66 @@ CORD compile(env_t *env, ast_t *ast) else if (pointer_depth > 1) code_err(call->self, "I expected "article" "name" pointer here, not a nested "name" pointer"); \ } while (0) switch (self_value_t->tag) { - case ArrayType: { - type_t *item_t = Match(self_value_t, ArrayType)->item_type; + case ListType: { + type_t *item_t = Match(self_value_t, ListType)->item_type; CORD padded_item_size = CORD_all("sizeof(", compile_type(item_t), ")"); if (streq(call->name, "insert")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="item", .type=item_t, .next=new(arg_t, .name="at", .type=INT_TYPE, .default_val=FakeAST(Int, .str="0"))); - return CORD_all("Array$insert_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$insert_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "insert_all")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="items", .type=self_value_t, .next=new(arg_t, .name="at", .type=INT_TYPE, .default_val=FakeAST(Int, .str="0"))); - return CORD_all("Array$insert_all(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$insert_all(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "remove_at")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="index", .type=INT_TYPE, .default_val=FakeAST(Int, .str="-1"), .next=new(arg_t, .name="count", .type=INT_TYPE, .default_val=FakeAST(Int, .str="1"))); - return CORD_all("Array$remove_at(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$remove_at(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "remove_item")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="item", .type=item_t, .next=new(arg_t, .name="max_count", .type=INT_TYPE, .default_val=FakeAST(Int, .str="-1"))); - return CORD_all("Array$remove_item_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$remove_item_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", compile_type_info(self_value_t), ")"); } else if (streq(call->name, "has")) { self = compile_to_pointer_depth(env, call->self, 0, false); arg_t *arg_spec = new(arg_t, .name="item", .type=item_t); - return CORD_all("Array$has_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$has_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", compile_type_info(self_value_t), ")"); } else if (streq(call->name, "sample")) { type_t *random_num_type = parse_type_string(env, "func(->Num)?"); self = compile_to_pointer_depth(env, call->self, 0, false); arg_t *arg_spec = new(arg_t, .name="count", .type=INT_TYPE, - .next=new(arg_t, .name="weights", .type=Type(ArrayType, .item_type=Type(NumType, .bits=TYPE_NBITS64)), + .next=new(arg_t, .name="weights", .type=Type(ListType, .item_type=Type(NumType, .bits=TYPE_NBITS64)), .default_val=FakeAST(None), .next=new(arg_t, .name="random", .type=random_num_type, .default_val=FakeAST(None)))); - return CORD_all("Array$sample(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", + return CORD_all("List$sample(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "shuffle")) { type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?"); - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="random", .type=random_int64_type, .default_val=FakeAST(None)); - return CORD_all("Array$shuffle(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); + return CORD_all("List$shuffle(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "shuffled")) { type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?"); self = compile_to_pointer_depth(env, call->self, 0, false); arg_t *arg_spec = new(arg_t, .name="random", .type=random_int64_type, .default_val=FakeAST(None)); - return CORD_all("Array$shuffled(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); + return CORD_all("List$shuffled(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "random")) { type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?"); self = compile_to_pointer_depth(env, call->self, 0, false); arg_t *arg_spec = new(arg_t, .name="random", .type=random_int64_type, .default_val=FakeAST(None)); - return CORD_all("Array$random_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", compile_type(item_t), ")"); + return CORD_all("List$random_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", compile_type(item_t), ")"); } else if (streq(call->name, "sort") || streq(call->name, "sorted")) { if (streq(call->name, "sort")) - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); else self = compile_to_pointer_depth(env, call->self, 0, false); CORD comparison; @@ -3120,9 +3120,9 @@ CORD compile(env_t *env, ast_t *ast) } else { comparison = CORD_all("((Closure_t){.fn=generic_compare, .userdata=(void*)", compile_type_info(item_t), "})"); } - return CORD_all("Array$", call->name, "(", self, ", ", comparison, ", ", padded_item_size, ")"); + return CORD_all("List$", call->name, "(", self, ", ", comparison, ", ", padded_item_size, ")"); } else if (streq(call->name, "heapify")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); CORD comparison; if (call->args) { type_t *item_ptr = Type(PointerType, .pointed=item_t, .is_stack=true); @@ -3132,9 +3132,9 @@ CORD compile(env_t *env, ast_t *ast) } else { comparison = CORD_all("((Closure_t){.fn=generic_compare, .userdata=(void*)", compile_type_info(item_t), "})"); } - return CORD_all("Array$heapify(", self, ", ", comparison, ", ", padded_item_size, ")"); + return CORD_all("List$heapify(", self, ", ", comparison, ", ", padded_item_size, ")"); } else if (streq(call->name, "heap_push")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); type_t *item_ptr = Type(PointerType, .pointed=item_t, .is_stack=true); type_t *fn_t = NewFunctionType(Type(IntType, .bits=TYPE_IBITS32), {.name="x", .type=item_ptr}, {.name="y", .type=item_ptr}); ast_t *default_cmp = LiteralCode(CORD_all("((Closure_t){.fn=generic_compare, .userdata=(void*)", @@ -3143,9 +3143,9 @@ CORD compile(env_t *env, ast_t *ast) arg_t *arg_spec = new(arg_t, .name="item", .type=item_t, .next=new(arg_t, .name="by", .type=Type(ClosureType, .fn=fn_t), .default_val=default_cmp)); CORD arg_code = compile_arguments(env, ast, arg_spec, call->args); - return CORD_all("Array$heap_push_value(", self, ", ", arg_code, ", ", padded_item_size, ")"); + return CORD_all("List$heap_push_value(", self, ", ", arg_code, ", ", padded_item_size, ")"); } else if (streq(call->name, "heap_pop")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); type_t *item_ptr = Type(PointerType, .pointed=item_t, .is_stack=true); type_t *fn_t = NewFunctionType(Type(IntType, .bits=TYPE_IBITS32), {.name="x", .type=item_ptr}, {.name="y", .type=item_ptr}); ast_t *default_cmp = LiteralCode(CORD_all("((Closure_t){.fn=generic_compare, .userdata=(void*)", @@ -3153,7 +3153,7 @@ CORD compile(env_t *env, ast_t *ast) .type=Type(ClosureType, .fn=fn_t)); arg_t *arg_spec = new(arg_t, .name="by", .type=Type(ClosureType, .fn=fn_t), .default_val=default_cmp); CORD arg_code = compile_arguments(env, ast, arg_spec, call->args); - return CORD_all("Array$heap_pop_value(", self, ", ", arg_code, ", ", compile_type(item_t), ", _, ", + return CORD_all("List$heap_pop_value(", self, ", ", arg_code, ", ", compile_type(item_t), ", _, ", promote_to_optional(item_t, "_"), ", ", compile_none(item_t), ")"); } else if (streq(call->name, "binary_search")) { self = compile_to_pointer_depth(env, call->self, 0, call->args != NULL); @@ -3166,15 +3166,15 @@ CORD compile(env_t *env, ast_t *ast) arg_t *arg_spec = new(arg_t, .name="target", .type=item_t, .next=new(arg_t, .name="by", .type=Type(ClosureType, .fn=fn_t), .default_val=default_cmp)); CORD arg_code = compile_arguments(env, ast, arg_spec, call->args); - return CORD_all("Array$binary_search_value(", self, ", ", arg_code, ")"); + return CORD_all("List$binary_search_value(", self, ", ", arg_code, ")"); } else if (streq(call->name, "clear")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); (void)compile_arguments(env, ast, NULL, call->args); - return CORD_all("Array$clear(", self, ")"); + return CORD_all("List$clear(", self, ")"); } else if (streq(call->name, "find")) { self = compile_to_pointer_depth(env, call->self, 0, false); arg_t *arg_spec = new(arg_t, .name="item", .type=item_t); - return CORD_all("Array$find_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), + return CORD_all("List$find_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", compile_type_info(self_value_t), ")"); } else if (streq(call->name, "first")) { self = compile_to_pointer_depth(env, call->self, 0, call->args != NULL); @@ -3182,38 +3182,38 @@ CORD compile(env_t *env, ast_t *ast) type_t *predicate_type = Type( ClosureType, .fn=NewFunctionType(Type(BoolType), {.name="item", .type=item_ptr})); arg_t *arg_spec = new(arg_t, .name="predicate", .type=predicate_type); - return CORD_all("Array$first(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); + return CORD_all("List$first(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); } else if (streq(call->name, "from")) { self = compile_to_pointer_depth(env, call->self, 0, true); arg_t *arg_spec = new(arg_t, .name="first", .type=INT_TYPE); - return CORD_all("Array$from(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); + return CORD_all("List$from(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); } else if (streq(call->name, "to")) { self = compile_to_pointer_depth(env, call->self, 0, true); arg_t *arg_spec = new(arg_t, .name="last", .type=INT_TYPE); - return CORD_all("Array$to(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); + return CORD_all("List$to(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")"); } else if (streq(call->name, "by")) { self = compile_to_pointer_depth(env, call->self, 0, true); arg_t *arg_spec = new(arg_t, .name="stride", .type=INT_TYPE); - return CORD_all("Array$by(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); + return CORD_all("List$by(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size, ")"); } else if (streq(call->name, "reversed")) { self = compile_to_pointer_depth(env, call->self, 0, true); (void)compile_arguments(env, ast, NULL, call->args); - return CORD_all("Array$reversed(", self, ", ", padded_item_size, ")"); + return CORD_all("List$reversed(", self, ", ", padded_item_size, ")"); } else if (streq(call->name, "unique")) { self = compile_to_pointer_depth(env, call->self, 0, false); (void)compile_arguments(env, ast, NULL, call->args); return CORD_all("Table$from_entries(", self, ", Set$info(", compile_type_info(item_t), "))"); } else if (streq(call->name, "pop")) { - EXPECT_POINTER("an", "array"); + EXPECT_POINTER("a", "list"); arg_t *arg_spec = new(arg_t, .name="index", .type=INT_TYPE, .default_val=FakeAST(Int, "-1")); CORD index = compile_arguments(env, ast, arg_spec, call->args); - return CORD_all("Array$pop(", self, ", ", index, ", ", compile_type(item_t), ", _, ", + return CORD_all("List$pop(", self, ", ", index, ", ", compile_type(item_t), ", _, ", promote_to_optional(item_t, "_"), ", ", compile_none(item_t), ")"); } else if (streq(call->name, "counts")) { self = compile_to_pointer_depth(env, call->self, 0, false); (void)compile_arguments(env, ast, NULL, call->args); - return CORD_all("Array$counts(", self, ", ", compile_type_info(self_value_t), ")"); - } else code_err(ast, "There is no '", call->name, "' method for arrays"); + return CORD_all("List$counts(", self, ", ", compile_type_info(self_value_t), ")"); + } else code_err(ast, "There is no '", call->name, "' method for lists"); } case SetType: { auto set = Match(self_value_t, SetType); @@ -3229,9 +3229,9 @@ CORD compile(env_t *env, ast_t *ast) compile_type_info(self_value_t), ")"); } else if (streq(call->name, "add_all")) { EXPECT_POINTER("a", "set"); - arg_t *arg_spec = new(arg_t, .name="items", .type=Type(ArrayType, .item_type=Match(self_value_t, SetType)->item_type)); + arg_t *arg_spec = new(arg_t, .name="items", .type=Type(ListType, .item_type=Match(self_value_t, SetType)->item_type)); return CORD_all("({ Table_t *set = ", self, "; ", - "Array_t to_add = ", compile_arguments(env, ast, arg_spec, call->args), "; ", + "List_t to_add = ", compile_arguments(env, ast, arg_spec, call->args), "; ", "for (int64_t i = 0; i < to_add.length; i++)\n" "Table$set(set, to_add.data + i*to_add.stride, NULL, ", compile_type_info(self_value_t), ");\n", "(void)0; })"); @@ -3242,9 +3242,9 @@ CORD compile(env_t *env, ast_t *ast) compile_type_info(self_value_t), ")"); } else if (streq(call->name, "remove_all")) { EXPECT_POINTER("a", "set"); - arg_t *arg_spec = new(arg_t, .name="items", .type=Type(ArrayType, .item_type=Match(self_value_t, SetType)->item_type)); + arg_t *arg_spec = new(arg_t, .name="items", .type=Type(ListType, .item_type=Match(self_value_t, SetType)->item_type)); return CORD_all("({ Table_t *set = ", self, "; ", - "Array_t to_add = ", compile_arguments(env, ast, arg_spec, call->args), "; ", + "List_t to_add = ", compile_arguments(env, ast, arg_spec, call->args), "; ", "for (int64_t i = 0; i < to_add.length; i++)\n" "Table$remove(set, to_add.data + i*to_add.stride, ", compile_type_info(self_value_t), ");\n", "(void)0; })"); @@ -3417,8 +3417,8 @@ CORD compile(env_t *env, ast_t *ast) case Deserialize: { ast_t *value = Match(ast, Deserialize)->value; type_t *value_type = get_type(env, value); - if (!type_eq(value_type, Type(ArrayType, Type(ByteType)))) - code_err(value, "This value should be an array of bytes, not a ", type_to_str(value_type)); + if (!type_eq(value_type, Type(ListType, Type(ByteType)))) + code_err(value, "This value should be a list of bytes, not a ", type_to_str(value_type)); type_t *t = parse_type_ast(env, Match(ast, Deserialize)->type); return CORD_all("({ ", compile_declaration(t, "deserialized"), ";\n" "generic_deserialize(", compile(env, value), ", &deserialized, ", compile_type_info(t), ");\n" @@ -3716,14 +3716,14 @@ CORD compile(env_t *env, ast_t *ast) } code_err(ast, "The field '", f->field, "' is not a valid tag name of ", type_to_str(value_t)); } - case ArrayType: { + case ListType: { if (streq(f->field, "length")) return CORD_all("Int$from_int64((", compile_to_pointer_depth(env, f->fielded, 0, false), ").length)"); - code_err(ast, "There is no ", f->field, " field on arrays"); + code_err(ast, "There is no ", f->field, " field on lists"); } case SetType: { if (streq(f->field, "items")) - return CORD_all("ARRAY_COPY((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries)"); + return CORD_all("LIST_COPY((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries)"); else if (streq(f->field, "length")) return CORD_all("Int$from_int64((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries.length)"); code_err(ast, "There is no '", f->field, "' field on sets"); @@ -3732,13 +3732,13 @@ CORD compile(env_t *env, ast_t *ast) if (streq(f->field, "length")) { return CORD_all("Int$from_int64((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries.length)"); } else if (streq(f->field, "keys")) { - return CORD_all("ARRAY_COPY((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries)"); + return CORD_all("LIST_COPY((", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries)"); } else if (streq(f->field, "values")) { auto table = Match(value_t, TableType); CORD offset = CORD_all("offsetof(struct { ", compile_declaration(table->key_type, "k"), "; ", compile_declaration(table->value_type, "v"), "; }, v)"); - return CORD_all("({ Array_t *entries = &(", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries;\n" - "ARRAY_INCREF(*entries);\n" - "Array_t values = *entries;\n" + return CORD_all("({ List_t *entries = &(", compile_to_pointer_depth(env, f->fielded, 0, false), ").entries;\n" + "LIST_INCREF(*entries);\n" + "List_t values = *entries;\n" "values.data += ", offset, ";\n" "values; })"); } else if (streq(f->field, "fallback")) { @@ -3762,8 +3762,8 @@ CORD compile(env_t *env, ast_t *ast) if (indexed_type->tag != PointerType) code_err(ast, "Only pointers can use the '[]' operator to dereference the entire value."); auto ptr = Match(indexed_type, PointerType); - if (ptr->pointed->tag == ArrayType) { - return CORD_all("*({ Array_t *arr = ", compile(env, indexing->indexed), "; ARRAY_INCREF(*arr); arr; })"); + if (ptr->pointed->tag == ListType) { + return CORD_all("*({ List_t *list = ", compile(env, indexing->indexed), "; LIST_INCREF(*list); list; })"); } else if (ptr->pointed->tag == TableType || ptr->pointed->tag == SetType) { return CORD_all("*({ Table_t *t = ", compile(env, indexing->indexed), "; TABLE_INCREF(*t); t; })"); } else { @@ -3773,20 +3773,20 @@ CORD compile(env_t *env, ast_t *ast) type_t *container_t = value_type(indexed_type); type_t *index_t = get_type(env, indexing->index); - if (container_t->tag == ArrayType) { + if (container_t->tag == ListType) { if (index_t->tag != IntType && index_t->tag != BigIntType && index_t->tag != ByteType) - code_err(indexing->index, "Arrays can only be indexed by integers, not ", type_to_str(index_t)); - type_t *item_type = Match(container_t, ArrayType)->item_type; - CORD arr = compile_to_pointer_depth(env, indexing->indexed, 0, false); + code_err(indexing->index, "Lists can only be indexed by integers, not ", type_to_str(index_t)); + type_t *item_type = Match(container_t, ListType)->item_type; + CORD list = compile_to_pointer_depth(env, indexing->indexed, 0, false); file_t *f = indexing->index->file; CORD index_code = indexing->index->tag == Int ? compile_int_to_type(env, indexing->index, Type(IntType, .bits=TYPE_IBITS64)) : (index_t->tag == BigIntType ? CORD_all("Int64$from_int(", compile(env, indexing->index), ", no)") : CORD_all("(Int64_t)(", compile(env, indexing->index), ")")); if (indexing->unchecked) - return CORD_all("Array_get_unchecked(", compile_type(item_type), ", ", arr, ", ", index_code, ")"); + return CORD_all("List_get_unchecked(", compile_type(item_type), ", ", list, ", ", index_code, ")"); else - return CORD_all("Array_get(", compile_type(item_type), ", ", arr, ", ", index_code, ", ", + return CORD_all("List_get(", compile_type(item_type), ", ", list, ", ", index_code, ", ", CORD_asprintf("%ld", (int64_t)(indexing->index->start - f->text)), ", ", CORD_asprintf("%ld", (int64_t)(indexing->index->end - f->text)), ")"); @@ -3859,9 +3859,9 @@ CORD compile_type_info(type_t *t) auto e = Match(t, EnumType); return CORD_all("(&", namespace_prefix(e->env, e->env->namespace->parent), e->name, "$$info)"); } - case ArrayType: { - type_t *item_t = Match(t, ArrayType)->item_type; - return CORD_all("Array$info(", compile_type_info(item_t), ")"); + case ListType: { + type_t *item_t = Match(t, ListType)->item_type; + return CORD_all("List$info(", compile_type_info(item_t), ")"); } case SetType: { type_t *item_type = Match(t, SetType)->item_type; @@ -3950,7 +3950,7 @@ CORD compile_cli_arg_call(env_t *env, CORD fn_name, type_t *fn_type) } else { if (t->tag == BoolType || (t->tag == OptionalType && Match(t, OptionalType)->type->tag == BoolType)) usage = CORD_all(usage, "[--", flag, "]"); - else if (t->tag == ArrayType) + else if (t->tag == ListType) usage = CORD_all(usage, "[--", flag, " ", get_flag_options(t, "|"), "]"); else usage = CORD_all(usage, "[--", flag, "=", get_flag_options(t, "|"), "]"); @@ -3960,7 +3960,7 @@ CORD compile_cli_arg_call(env_t *env, CORD fn_name, type_t *fn_type) usage = CORD_all(usage, "<--", flag, "|--no-", flag, ">"); else if (t->tag == EnumType) usage = CORD_all(usage, get_flag_options(t, "|")); - else if (t->tag == ArrayType) + else if (t->tag == ListType) usage = CORD_all(usage, "[", flag, "...]"); else usage = CORD_all(usage, "<", flag, ">"); diff --git a/src/environment.c b/src/environment.c index 8084758e..0d55be9c 100644 --- a/src/environment.c +++ b/src/environment.c @@ -76,20 +76,20 @@ env_t *global_env(void) type_t *type; CORD typename; CORD typeinfo; - Array_t namespace; + List_t namespace; } global_types[] = { {"Void", Type(VoidType), "Void_t", "Void$info", {}}, {"Abort", Type(AbortType), "void", "Abort$info", {}}, {"Memory", Type(MemoryType), "Memory_t", "Memory$info", {}}, - {"Bool", Type(BoolType), "Bool_t", "Bool$info", TypedArray(ns_entry_t, + {"Bool", Type(BoolType), "Bool_t", "Bool$info", TypedList(ns_entry_t, {"parse", "Bool$parse", "func(text:Text -> Bool?)"}, )}, - {"Byte", Type(ByteType), "Byte_t", "Byte$info", TypedArray(ns_entry_t, + {"Byte", Type(ByteType), "Byte_t", "Byte$info", TypedList(ns_entry_t, {"max", "Byte$max", "Byte"}, {"hex", "Byte$hex", "func(byte:Byte, uppercase=yes, prefix=no -> Text)"}, {"min", "Byte$min", "Byte"}, )}, - {"Int", Type(BigIntType), "Int_t", "Int$info", TypedArray(ns_entry_t, + {"Int", Type(BigIntType), "Int_t", "Int$info", TypedList(ns_entry_t, {"abs", "Int$abs", "func(x:Int -> Int)"}, {"bit_and", "Int$bit_and", "func(x,y:Int -> Int)"}, {"bit_or", "Int$bit_or", "func(x,y:Int -> Int)"}, @@ -124,7 +124,7 @@ env_t *global_env(void) {"times", "Int$times", "func(x,y:Int -> Int)"}, {"to", "Int$to", "func(first:Int,last:Int,step:Int?=none -> func(->Int?))"}, )}, - {"Int64", Type(IntType, .bits=TYPE_IBITS64), "Int64_t", "Int64$info", TypedArray(ns_entry_t, + {"Int64", Type(IntType, .bits=TYPE_IBITS64), "Int64_t", "Int64$info", TypedList(ns_entry_t, {"abs", "labs", "func(i:Int64 -> Int64)"}, {"bits", "Int64$bits", "func(x:Int64 -> [Bool])"}, {"clamped", "Int64$clamped", "func(x,low,high:Int64 -> Int64)"}, @@ -145,7 +145,7 @@ env_t *global_env(void) {"wrapping_minus", "Int64$wrapping_minus", "func(x:Int64,y:Int64 -> Int64)"}, {"wrapping_plus", "Int64$wrapping_plus", "func(x:Int64,y:Int64 -> Int64)"}, )}, - {"Int32", Type(IntType, .bits=TYPE_IBITS32), "Int32_t", "Int32$info", TypedArray(ns_entry_t, + {"Int32", Type(IntType, .bits=TYPE_IBITS32), "Int32_t", "Int32$info", TypedList(ns_entry_t, {"abs", "abs", "func(i:Int32 -> Int32)"}, {"bits", "Int32$bits", "func(x:Int32 -> [Bool])"}, {"clamped", "Int32$clamped", "func(x,low,high:Int32 -> Int32)"}, @@ -166,7 +166,7 @@ env_t *global_env(void) {"wrapping_minus", "Int32$wrapping_minus", "func(x:Int32,y:Int32 -> Int32)"}, {"wrapping_plus", "Int32$wrapping_plus", "func(x:Int32,y:Int32 -> Int32)"}, )}, - {"Int16", Type(IntType, .bits=TYPE_IBITS16), "Int16_t", "Int16$info", TypedArray(ns_entry_t, + {"Int16", Type(IntType, .bits=TYPE_IBITS16), "Int16_t", "Int16$info", TypedList(ns_entry_t, {"abs", "abs", "func(i:Int16 -> Int16)"}, {"bits", "Int16$bits", "func(x:Int16 -> [Bool])"}, {"clamped", "Int16$clamped", "func(x,low,high:Int16 -> Int16)"}, @@ -187,7 +187,7 @@ env_t *global_env(void) {"wrapping_minus", "Int16$wrapping_minus", "func(x:Int16,y:Int16 -> Int16)"}, {"wrapping_plus", "Int16$wrapping_plus", "func(x:Int16,y:Int16 -> Int16)"}, )}, - {"Int8", Type(IntType, .bits=TYPE_IBITS8), "Int8_t", "Int8$info", TypedArray(ns_entry_t, + {"Int8", Type(IntType, .bits=TYPE_IBITS8), "Int8_t", "Int8$info", TypedList(ns_entry_t, {"abs", "abs", "func(i:Int8 -> Int8)"}, {"bits", "Int8$bits", "func(x:Int8 -> [Bool])"}, {"clamped", "Int8$clamped", "func(x,low,high:Int8 -> Int8)"}, @@ -212,7 +212,7 @@ env_t *global_env(void) #define F(name) {#name, #name, "func(n:Num -> Num)"} #define F_opt(name) {#name, #name, "func(n:Num -> Num?)"} #define F2(name) {#name, #name, "func(x,y:Num -> Num)"} - {"Num", Type(NumType, .bits=TYPE_NBITS64), "Num_t", "Num$info", TypedArray(ns_entry_t, + {"Num", Type(NumType, .bits=TYPE_NBITS64), "Num_t", "Num$info", TypedList(ns_entry_t, {"near", "Num$near", "func(x,y:Num, ratio=1e-9, min_epsilon=1e-9 -> Bool)"}, {"clamped", "Num$clamped", "func(x,low,high:Num -> Num)"}, {"format", "Num$format", "func(n:Num, precision=16 -> Text)"}, @@ -244,7 +244,7 @@ env_t *global_env(void) #define F(name) {#name, #name"f", "func(n:Num32 -> Num32)"} #define F_opt(name) {#name, #name"f", "func(n:Num32 -> Num32?)"} #define F2(name) {#name, #name"f", "func(x,y:Num32 -> Num32)"} - {"Num32", Type(NumType, .bits=TYPE_NBITS32), "Num32_t", "Num32$info", TypedArray(ns_entry_t, + {"Num32", Type(NumType, .bits=TYPE_NBITS32), "Num32_t", "Num32$info", TypedList(ns_entry_t, {"near", "Num32$near", "func(x,y:Num32, ratio=Num32(1e-9), min_epsilon=Num32(1e-9) -> Bool)"}, {"clamped", "Num32$clamped", "func(x,low,high:Num32 -> Num32)"}, {"format", "Num32$format", "func(n:Num32, precision=8 -> Text)"}, @@ -268,19 +268,19 @@ env_t *global_env(void) F_opt(tan), F(tanh), F_opt(tgamma), F(trunc), F_opt(y0), F_opt(y1), F2(atan2), F2(copysign), F2(fdim), F2(hypot), F2(nextafter), )}, - {"CString", Type(CStringType), "char*", "CString$info", TypedArray(ns_entry_t, + {"CString", Type(CStringType), "char*", "CString$info", TypedList(ns_entry_t, {"as_text", "CString$as_text_simple", "func(str:CString -> Text)"}, )}, #undef F2 #undef F_opt #undef F #undef C - {"PathType", PATH_TYPE_TYPE, "PathType_t", "PathType$info", TypedArray(ns_entry_t, + {"PathType", PATH_TYPE_TYPE, "PathType_t", "PathType$info", TypedList(ns_entry_t, {"Relative", "((PathType_t){.$tag=PATH_RELATIVE})", "PathType"}, {"Absolute", "((PathType_t){.$tag=PATH_ABSOLUTE})", "PathType"}, {"Home", "((PathType_t){.$tag=PATH_HOME})", "PathType"}, )}, - {"Path", PATH_TYPE, "Path_t", "Path$info", TypedArray(ns_entry_t, + {"Path", PATH_TYPE, "Path_t", "Path$info", TypedList(ns_entry_t, {"accessed", "Path$accessed", "func(path:Path, follow_symlinks=yes -> Int64?)"}, {"append", "Path$append", "func(path:Path, text:Text, permissions=Int32(0o644))"}, {"append_bytes", "Path$append_bytes", "func(path:Path, bytes:[Byte], permissions=Int32(0o644))"}, @@ -322,7 +322,7 @@ env_t *global_env(void) {"write_unique", "Path$write_unique", "func(path:Path, text:Text -> Path)"}, {"write_unique_bytes", "Path$write_unique_bytes", "func(path:Path, bytes:[Byte] -> Path)"}, )}, - {"Text", TEXT_TYPE, "Text_t", "Text$info", TypedArray(ns_entry_t, + {"Text", TEXT_TYPE, "Text_t", "Text$info", TypedList(ns_entry_t, {"as_c_string", "Text$as_c_string", "func(text:Text -> CString)"}, {"at", "Text$cluster", "func(text:Text, index:Int -> Text)"}, {"by_line", "Text$by_line", "func(text:Text -> func(->Text?))"}, @@ -406,7 +406,7 @@ env_t *global_env(void) struct { const char *c_name, *type_str; } constructor_infos[] = {__VA_ARGS__}; \ for (size_t i = 0; i < sizeof(constructor_infos)/sizeof(constructor_infos[0]); i++) { \ type_t *t = parse_type_string(ns_env, constructor_infos[i].type_str); \ - Array$insert(&ns_env->namespace->constructors, \ + List$insert(&ns_env->namespace->constructors, \ ((binding_t[1]){{.code=constructor_infos[i].c_name, \ .type=Match(t, ClosureType)->fn}}), I(0), sizeof(binding_t)); \ } \ @@ -597,8 +597,8 @@ env_t *for_scope(env_t *env, ast_t *ast) env_t *scope = fresh_scope(env); switch (iter_t->tag) { - case ArrayType: { - type_t *item_t = Match(iter_t, ArrayType)->item_type; + case ListType: { + type_t *item_t = Match(iter_t, ListType)->item_type; const char *vars[2] = {}; int64_t num_vars = 0; for (ast_list_t *var = for_->vars; var; var = var->next) { @@ -672,7 +672,7 @@ env_t *get_namespace_by_type(env_t *env, type_t *t) { t = value_type(t); switch (t->tag) { - case ArrayType: return NULL; + case ListType: return NULL; case TableType: return NULL; case CStringType: case BoolType: case IntType: case BigIntType: case NumType: case ByteType: { @@ -730,7 +730,7 @@ PUREFUNC binding_t *get_constructor(env_t *env, type_t *t, arg_ast_t *args) { env_t *type_env = get_namespace_by_type(env, t); if (!type_env) return NULL; - Array_t constructors = type_env->namespace->constructors; + List_t constructors = type_env->namespace->constructors; // Prioritize exact matches: for (int64_t i = constructors.length-1; i >= 0; i--) { binding_t *b = constructors.data + i*constructors.stride; diff --git a/src/environment.h b/src/environment.h index cbaae09b..1484a4c4 100644 --- a/src/environment.h +++ b/src/environment.h @@ -33,7 +33,7 @@ typedef struct loop_ctx_s { typedef struct namespace_s { const char *name; - Array_t constructors; + List_t constructors; struct namespace_s *parent; } namespace_t; diff --git a/src/parse.c b/src/parse.c index b9a695b9..d142e780 100644 --- a/src/parse.c +++ b/src/parse.c @@ -89,7 +89,7 @@ static ast_t *parse_non_optional_suffix(parse_ctx_t *ctx, ast_t *lhs); static ast_t *parse_optional_conditional_suffix(parse_ctx_t *ctx, ast_t *stmt); static ast_t *parse_optional_suffix(parse_ctx_t *ctx, ast_t *lhs); static arg_ast_t *parse_args(parse_ctx_t *ctx, const char **pos); -static type_ast_t *parse_array_type(parse_ctx_t *ctx, const char *pos); +static type_ast_t *parse_list_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_func_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_non_optional_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_pointer_type(parse_ctx_t *ctx, const char *pos); @@ -97,7 +97,7 @@ static type_ast_t *parse_set_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_table_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_type(parse_ctx_t *ctx, const char *pos); static type_ast_t *parse_type_name(parse_ctx_t *ctx, const char *pos); -static PARSER(parse_array); +static PARSER(parse_list); static PARSER(parse_assignment); static PARSER(parse_block); static PARSER(parse_bool); @@ -564,13 +564,13 @@ type_ast_t *parse_func_type(parse_ctx_t *ctx, const char *pos) { return NewTypeAST(ctx->file, start, pos, FunctionTypeAST, .args=args, .ret=ret); } -type_ast_t *parse_array_type(parse_ctx_t *ctx, const char *pos) { +type_ast_t *parse_list_type(parse_ctx_t *ctx, const char *pos) { const char *start = pos; if (!match(&pos, "[")) return NULL; type_ast_t *type = expect(ctx, start, &pos, parse_type, - "I couldn't parse an array item type after this point"); - expect_closing(ctx, &pos, "]", "I wasn't able to parse the rest of this array type"); - return NewTypeAST(ctx->file, start, pos, ArrayTypeAST, .item=type); + "I couldn't parse a list item type after this point"); + expect_closing(ctx, &pos, "]", "I wasn't able to parse the rest of this list type"); + return NewTypeAST(ctx->file, start, pos, ListTypeAST, .item=type); } type_ast_t *parse_pointer_type(parse_ctx_t *ctx, const char *pos) { @@ -614,7 +614,7 @@ type_ast_t *parse_non_optional_type(parse_ctx_t *ctx, const char *pos) { type_ast_t *type = NULL; bool success = (false || (type=parse_pointer_type(ctx, pos)) - || (type=parse_array_type(ctx, pos)) + || (type=parse_list_type(ctx, pos)) || (type=parse_table_type(ctx, pos)) || (type=parse_set_type(ctx, pos)) || (type=parse_type_name(ctx, pos)) @@ -698,7 +698,7 @@ static INLINE bool match_separator(const char **pos) { // Either comma or newlin } } -PARSER(parse_array) { +PARSER(parse_list) { const char *start = pos; if (!match(&pos, "[")) return NULL; @@ -719,10 +719,10 @@ PARSER(parse_array) { break; } whitespace(&pos); - expect_closing(ctx, &pos, "]", "I wasn't able to parse the rest of this array"); + expect_closing(ctx, &pos, "]", "I wasn't able to parse the rest of this list"); REVERSE_LIST(items); - return NewAST(ctx->file, start, pos, Array, .items=items); + return NewAST(ctx->file, start, pos, List, .items=items); } PARSER(parse_table) { @@ -1466,7 +1466,7 @@ PARSER(parse_term_no_suffix) { || (term=parse_set(ctx, pos)) || (term=parse_deserialize(ctx, pos)) || (term=parse_var(ctx, pos)) - || (term=parse_array(ctx, pos)) + || (term=parse_list(ctx, pos)) || (term=parse_reduction(ctx, pos)) || (term=parse_pass(ctx, pos)) || (term=parse_defer(ctx, pos)) diff --git a/src/repl.c b/src/repl.c index 463e7ff8..bd08a3e4 100644 --- a/src/repl.c +++ b/src/repl.c @@ -128,10 +128,10 @@ const TypeInfo_t *type_to_type_info(type_t *t) default: print_err("Invalid bits"); } case TextType: return &Text$info; - case ArrayType: { - const TypeInfo_t *item_info = type_to_type_info(Match(t, ArrayType)->item_type); - TypeInfo_t array_info = *Array$info(item_info); - return memcpy(GC_MALLOC(sizeof(TypeInfo_t)), &array_info, sizeof(TypeInfo_t)); + case ListType: { + const TypeInfo_t *item_info = type_to_type_info(Match(t, ListType)->item_type); + TypeInfo_t list_info = *List$info(item_info); + return memcpy(GC_MALLOC(sizeof(TypeInfo_t)), &list_info, sizeof(TypeInfo_t)); } case TableType: { const TypeInfo_t *key_info = type_to_type_info(Match(t, TableType)->key_type); @@ -391,17 +391,17 @@ void eval(env_t *env, ast_t *ast, void *dest) type_t *indexed_t = get_type(env, index->indexed); // type_t *index_t = get_type(env, index->index); switch (indexed_t->tag) { - case ArrayType: { - Array_t arr; - eval(env, index->indexed, &arr); + case ListType: { + List_t list; + eval(env, index->indexed, &list); int64_t raw_index = Int64$from_int(ast_to_int(env, index->index), false); int64_t index_int = raw_index; - if (index_int < 1) index_int = arr.length + index_int + 1; - if (index_int < 1 || index_int > arr.length) + if (index_int < 1) index_int = list.length + index_int + 1; + if (index_int < 1 || index_int > list.length) print_err(raw_index, - " is an invalid index for an array with length ", (int64_t)arr.length); - size_t item_size = type_size(Match(indexed_t, ArrayType)->item_type); - memcpy(dest, arr.data + arr.stride*(index_int-1), item_size); + " is an invalid index for a list with length ", (int64_t)list.length); + size_t item_size = type_size(Match(indexed_t, ListType)->item_type); + memcpy(dest, list.data + list.stride*(index_int-1), item_size); break; } case TableType: { @@ -427,16 +427,16 @@ void eval(env_t *env, ast_t *ast, void *dest) } break; } - case Array: { - assert(t->tag == ArrayType); - Array_t arr = {}; - size_t item_size = type_size(Match(t, ArrayType)->item_type); + case List: { + assert(t->tag == ListType); + List_t list = {}; + size_t item_size = type_size(Match(t, ListType)->item_type); char item_buf[item_size]; - for (ast_list_t *item = Match(ast, Array)->items; item; item = item->next) { + for (ast_list_t *item = Match(ast, List)->items; item; item = item->next) { eval(env, item->ast, item_buf); - Array$insert(&arr, item_buf, I(0), (int64_t)type_size(Match(t, ArrayType)->item_type)); + List$insert(&list, item_buf, I(0), (int64_t)type_size(Match(t, ListType)->item_type)); } - memcpy(dest, &arr, sizeof(Array_t)); + memcpy(dest, &list, sizeof(List_t)); break; } case Table: { diff --git a/src/stdlib/README.md b/src/stdlib/README.md index 1c72d3d3..671d330a 100644 --- a/src/stdlib/README.md +++ b/src/stdlib/README.md @@ -16,7 +16,7 @@ some common functionality. ## Core Data Types - Datatypes (type definitions): [datatypes.h](datatypes.h), [datatypes.c](datatypes.c) -- Arrays: [arrays.h](arrays.h), [arrays.c](arrays.c) +- Lists: [lists.h](lists.h), [lists.c](lists.c) - Bools: [bools.h](bools.h), [bools.c](bools.c) - Bytes: [bytes.h](bytes.h), [bytes.c](bytes.c) - C Strings: [c_strings.h](c_strings.h), [c_strings.c](c_strings.c) diff --git a/src/stdlib/arrays.c b/src/stdlib/arrays.c deleted file mode 100644 index c8b82cf4..00000000 --- a/src/stdlib/arrays.c +++ /dev/null @@ -1,813 +0,0 @@ -// Functions that operate on arrays - -#include -#include -#include -#include - -#include "arrays.h" -#include "integers.h" -#include "math.h" -#include "metamethods.h" -#include "optionals.h" -#include "tables.h" -#include "text.h" -#include "util.h" - -// Use inline version of siphash code: -#include "siphash.h" -#include "siphash-internals.h" - -PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info) -{ - int64_t size = info->ArrayInfo.item->size; - if (info->ArrayInfo.item->align > 1 && size % info->ArrayInfo.item->align) - errx(1, "Item size is not padded!"); - return size; -} - -// Replace the array's .data pointer with a new pointer to a copy of the -// data that is compacted and has a stride of exactly `padded_item_size` -public void Array$compact(Array_t *arr, int64_t padded_item_size) -{ - void *copy = NULL; - if (arr->length > 0) { - copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)arr->length * (size_t)padded_item_size) - : GC_MALLOC((size_t)arr->length * (size_t)padded_item_size); - if ((int64_t)arr->stride == padded_item_size) { - memcpy(copy, arr->data, (size_t)arr->length * (size_t)padded_item_size); - } else { - for (int64_t i = 0; i < arr->length; i++) - memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size); - } - } - *arr = (Array_t){ - .data=copy, - .length=arr->length, - .stride=padded_item_size, - .atomic=arr->atomic, - }; -} - -public void Array$insert(Array_t *arr, const void *item, Int_t int_index, int64_t padded_item_size) -{ - int64_t index = Int64$from_int(int_index, false); - if (index <= 0) index = arr->length + index + 1; - - if (index < 1) index = 1; - else if (index > (int64_t)arr->length + 1) - fail("Invalid insertion index ", index, " for an array with length ", (int64_t)arr->length); - - if (!arr->data) { - arr->free = 4; - arr->data = arr->atomic ? GC_MALLOC_ATOMIC((size_t)arr->free * (size_t)padded_item_size) - : GC_MALLOC((size_t)arr->free * (size_t)padded_item_size); - arr->stride = padded_item_size; - } else if (arr->free < 1 || arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) { - // Resize policy: +50% growth (clamped between 8 and ARRAY_MAX_FREE_ENTRIES) - arr->free = MIN(ARRAY_MAX_FREE_ENTRIES, MAX(8, arr->length)/2); - void *copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)(arr->length + arr->free) * (size_t)padded_item_size) - : GC_MALLOC((size_t)(arr->length + arr->free) * (size_t)padded_item_size); - for (int64_t i = 0; i < index-1; i++) - memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size); - for (int64_t i = index-1; i < (int64_t)arr->length; i++) - memcpy(copy + (i+1)*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size); - arr->data = copy; - arr->data_refcount = 0; - arr->stride = padded_item_size; - } else { - if (index != arr->length+1) - memmove( - arr->data + index*padded_item_size, - arr->data + (index-1)*padded_item_size, - (size_t)((arr->length - index + 1)*padded_item_size)); - } - assert(arr->free > 0); - --arr->free; - ++arr->length; - memcpy((void*)arr->data + (index-1)*padded_item_size, item, (size_t)padded_item_size); -} - -public void Array$insert_all(Array_t *arr, Array_t to_insert, Int_t int_index, int64_t padded_item_size) -{ - int64_t index = Int64$from_int(int_index, false); - if (to_insert.length == 0) - return; - - if (!arr->data) { - *arr = to_insert; - ARRAY_INCREF(*arr); - return; - } - - if (index < 1) index = arr->length + index + 1; - - if (index < 1) index = 1; - else if (index > (int64_t)arr->length + 1) - fail("Invalid insertion index ", index, " for an array with length ", (int64_t)arr->length); - - if ((int64_t)arr->free >= (int64_t)to_insert.length // Adequate free space - && arr->data_refcount == 0 // Not aliased memory - && (int64_t)arr->stride == padded_item_size) { // Contiguous array - // If we can fit this within the array's preallocated free space, do that: - arr->free -= to_insert.length; - arr->length += to_insert.length; - if (index != arr->length+1) - memmove((void*)arr->data + index*padded_item_size, - arr->data + (index-1)*padded_item_size, - (size_t)((arr->length - index + to_insert.length-1)*padded_item_size)); - for (int64_t i = 0; i < to_insert.length; i++) - memcpy((void*)arr->data + (index-1 + i)*padded_item_size, - to_insert.data + i*to_insert.stride, (size_t)padded_item_size); - } else { - // Otherwise, allocate a new chunk of memory for the array and populate it: - int64_t new_len = arr->length + to_insert.length; - arr->free = MIN(ARRAY_MAX_FREE_ENTRIES, MAX(8, new_len/4)); - void *data = arr->atomic ? GC_MALLOC_ATOMIC((size_t)((new_len + arr->free) * padded_item_size)) - : GC_MALLOC((size_t)((new_len + arr->free) * padded_item_size)); - void *p = data; - - // Copy first chunk of `arr` if needed: - if (index > 1) { - if (arr->stride == padded_item_size) { - memcpy(p, arr->data, (size_t)((index-1)*padded_item_size)); - p += (index-1)*padded_item_size; - } else { - for (int64_t i = 0; i < index-1; i++) { - memcpy(p, arr->data + arr->stride*i, (size_t)padded_item_size); - p += padded_item_size; - } - } - } - - // Copy `to_insert` - if (to_insert.stride == padded_item_size) { - memcpy(p, to_insert.data, (size_t)(to_insert.length*padded_item_size)); - p += to_insert.length*padded_item_size; - } else { - for (int64_t i = 0; i < index-1; i++) { - memcpy(p, to_insert.data + to_insert.stride*i, (size_t)padded_item_size); - p += padded_item_size; - } - } - - // Copy last chunk of `arr` if needed: - if (index < arr->length + 1) { - if (arr->stride == padded_item_size) { - memcpy(p, arr->data + padded_item_size*(index-1), (size_t)((arr->length - index + 1)*padded_item_size)); - p += (arr->length - index + 1)*padded_item_size; - } else { - for (int64_t i = index-1; i < arr->length-1; i++) { - memcpy(p, arr->data + arr->stride*i, (size_t)padded_item_size); - p += padded_item_size; - } - } - } - arr->length = new_len; - arr->stride = padded_item_size; - arr->data = data; - arr->data_refcount = 0; - } -} - -public void Array$remove_at(Array_t *arr, Int_t int_index, Int_t int_count, int64_t padded_item_size) -{ - int64_t index = Int64$from_int(int_index, false); - if (index < 1) index = arr->length + index + 1; - - int64_t count = Int64$from_int(int_count, false); - if (index < 1 || index > (int64_t)arr->length || count < 1) return; - - if (count > arr->length - index + 1) - count = (arr->length - index) + 1; - - if (index == 1) { - arr->data += arr->stride * count; - } else if (index + count > arr->length) { - arr->free += count; - } else if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) { - void *copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)((arr->length-1) * padded_item_size)) - : GC_MALLOC((size_t)((arr->length-1) * padded_item_size)); - for (int64_t src = 1, dest = 1; src <= (int64_t)arr->length; src++) { - if (src < index || src >= index + count) { - memcpy(copy + (dest - 1)*padded_item_size, arr->data + arr->stride*(src - 1), (size_t)padded_item_size); - ++dest; - } - } - arr->data = copy; - arr->free = 0; - arr->data_refcount = 0; - } else { - memmove((void*)arr->data + (index-1)*padded_item_size, arr->data + (index-1 + count)*padded_item_size, - (size_t)((arr->length - index + count - 1)*padded_item_size)); - arr->free += count; - } - arr->length -= count; - if (arr->length == 0) arr->data = NULL; -} - -public void Array$remove_item(Array_t *arr, void *item, Int_t max_removals, const TypeInfo_t *type) -{ - int64_t padded_item_size = get_padded_item_size(type); - const Int_t ZERO = (Int_t){.small=(0<<2)|1}; - const Int_t ONE = (Int_t){.small=(1<<2)|1}; - const TypeInfo_t *item_type = type->ArrayInfo.item; - for (int64_t i = 0; i < arr->length; ) { - if (max_removals.small == ZERO.small) // zero - break; - - if (generic_equal(item, arr->data + i*arr->stride, item_type)) { - Array$remove_at(arr, I(i+1), ONE, padded_item_size); - max_removals = Int$minus(max_removals, ONE); - } else { - i++; - } - } -} - -public OptionalInt_t Array$find(Array_t arr, void *item, const TypeInfo_t *type) -{ - const TypeInfo_t *item_type = type->ArrayInfo.item; - for (int64_t i = 0; i < arr.length; i++) { - if (generic_equal(item, arr.data + i*arr.stride, item_type)) - return I(i+1); - } - return NONE_INT; -} - -public OptionalInt_t Array$first(Array_t arr, Closure_t predicate) -{ - bool (*is_good)(void*, void*) = (void*)predicate.fn; - for (int64_t i = 0; i < arr.length; i++) { - if (is_good(arr.data + i*arr.stride, predicate.userdata)) - return I(i+1); - } - return NONE_INT; -} - -static Closure_t _sort_comparison = {.fn=NULL}; - -int _compare_closure(const void *a, const void *b) -{ - typedef int (*comparison_t)(const void*, const void*, void*); - return ((comparison_t)_sort_comparison.fn)(a, b, _sort_comparison.userdata); -} - -public void Array$sort(Array_t *arr, Closure_t comparison, int64_t padded_item_size) -{ - if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) - Array$compact(arr, padded_item_size); - - _sort_comparison = comparison; - qsort(arr->data, (size_t)arr->length, (size_t)padded_item_size, _compare_closure); -} - -public Array_t Array$sorted(Array_t arr, Closure_t comparison, int64_t padded_item_size) -{ - Array$compact(&arr, padded_item_size); - _sort_comparison = comparison; - qsort(arr.data, (size_t)arr.length, (size_t)padded_item_size, _compare_closure); - return arr; -} - -#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__) -static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) { - (void)flags; - arc4random_buf(buf, buflen); - return buflen; -} -#elif defined(__linux__) -// Use getrandom() -# include -#else - #error "Unsupported platform for secure random number generation" -#endif - -static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata) -{ - (void)userdata; - if (min > max) fail("Random minimum value (", min, ") is larger than the maximum value (", max, ")"); - if (min == max) return min; - uint64_t range = (uint64_t)max - (uint64_t)min + 1; - uint64_t min_r = -range % range; - uint64_t r; - for (;;) { - getrandom(&r, sizeof(r), 0); - if (r >= min_r) break; - } - return (int64_t)((uint64_t)min + (r % range)); -} - -public void Array$shuffle(Array_t *arr, OptionalClosure_t random_int64, int64_t padded_item_size) -{ - if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) - Array$compact(arr, padded_item_size); - - typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*); - rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64; - char tmp[padded_item_size]; - for (int64_t i = arr->length-1; i > 1; i--) { - int64_t j = rng_fn(0, i, random_int64.userdata); - if unlikely (j < 0 || j > arr->length-1) - fail("The provided random number function returned an invalid value: ", j, " (not between 0 and ", i, ")"); - memcpy(tmp, arr->data + i*padded_item_size, (size_t)padded_item_size); - memcpy((void*)arr->data + i*padded_item_size, arr->data + j*padded_item_size, (size_t)padded_item_size); - memcpy((void*)arr->data + j*padded_item_size, tmp, (size_t)padded_item_size); - } -} - -public Array_t Array$shuffled(Array_t arr, Closure_t random_int64, int64_t padded_item_size) -{ - Array$compact(&arr, padded_item_size); - Array$shuffle(&arr, random_int64, padded_item_size); - return arr; -} - -public void *Array$random(Array_t arr, OptionalClosure_t random_int64) -{ - if (arr.length == 0) - return NULL; // fail("Cannot get a random item from an empty array!"); - - typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*); - rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64; - int64_t index = rng_fn(0, arr.length-1, random_int64.userdata); - if unlikely (index < 0 || index > arr.length-1) - fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ", (int64_t)arr.length, ")"); - return arr.data + arr.stride*index; -} - -public Table_t Array$counts(Array_t arr, const TypeInfo_t *type) -{ - Table_t counts = {}; - const TypeInfo_t count_type = *Table$info(type->ArrayInfo.item, &Int$info); - for (int64_t i = 0; i < arr.length; i++) { - void *key = arr.data + i*arr.stride; - int64_t *count = Table$get(counts, key, &count_type); - int64_t val = count ? *count + 1 : 1; - Table$set(&counts, key, &val, &count_type); - } - return counts; -} - -static double _default_random_num(void *userdata) -{ - (void)userdata; - union { - Num_t num; - uint64_t bits; - } r = {.bits=0}, one = {.num=1.0}; - getrandom((uint8_t*)&r, sizeof(r), 0); - - // Set r.num to 1. - r.bits &= ~(0xFFFULL << 52); - r.bits |= (one.bits & (0xFFFULL << 52)); - return r.num - 1.0; -} - -public Array_t Array$sample(Array_t arr, Int_t int_n, Array_t weights, OptionalClosure_t random_num, int64_t padded_item_size) -{ - int64_t n = Int64$from_int(int_n, false); - if (n < 0) - fail("Cannot select a negative number of values"); - - if (n == 0) - return (Array_t){}; - - if (arr.length == 0) - fail("There are no elements in this array!"); - - if (weights.length != arr.length) - fail("Array has ", (int64_t)arr.length, " elements, but there are ", (int64_t)weights.length, " weights given"); - - double total = 0.0; - for (int64_t i = 0; i < weights.length && i < arr.length; i++) { - double weight = *(double*)(weights.data + weights.stride*i); - if (isinf(weight)) - fail("Infinite weight!"); - else if (isnan(weight)) - fail("NaN weight!"); - else if (weight < 0.0) - fail("Negative weight!"); - else - total += weight; - } - - if (isinf(total)) - fail("Sample weights have overflowed to infinity"); - - if (total == 0.0) - fail("None of the given weights are nonzero"); - - double inverse_average = (double)arr.length / total; - - struct { - int64_t alias; - double odds; - } aliases[arr.length]; - - for (int64_t i = 0; i < arr.length; i++) { - double weight = i >= weights.length ? 0.0 : *(double*)(weights.data + weights.stride*i); - aliases[i].odds = weight * inverse_average; - aliases[i].alias = -1; - } - - int64_t small = 0; - for (int64_t big = 0; big < arr.length; big++) { - while (aliases[big].odds >= 1.0) { - while (small < arr.length && (aliases[small].odds >= 1.0 || aliases[small].alias != -1)) - ++small; - - if (small >= arr.length) { - aliases[big].odds = 1.0; - aliases[big].alias = big; - break; - } - - aliases[small].alias = big; - aliases[big].odds = (aliases[small].odds + aliases[big].odds) - 1.0; - } - if (big < small) small = big; - } - - for (int64_t i = small; i < arr.length; i++) - if (aliases[i].alias == -1) - aliases[i].alias = i; - - typedef double (*rng_fn_t)(void*); - rng_fn_t rng_fn = random_num.fn ? (rng_fn_t)random_num.fn : _default_random_num; - - Array_t selected = { - .data=arr.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size)) : GC_MALLOC((size_t)(n * padded_item_size)), - .length=n, - .stride=padded_item_size, .atomic=arr.atomic}; - for (int64_t i = 0; i < n; i++) { - double r = rng_fn(random_num.userdata); - if unlikely (r < 0.0 || r >= 1.0) - fail("The random number function returned a value not between 0.0 (inclusive) and 1.0 (exclusive): ", r); - r *= (double)arr.length; - int64_t index = (int64_t)r; - assert(index >= 0 && index < arr.length); - if ((r - (double)index) > aliases[index].odds) - index = aliases[index].alias; - memcpy(selected.data + i*selected.stride, arr.data + index*arr.stride, (size_t)padded_item_size); - } - return selected; -} - -public Array_t Array$from(Array_t array, Int_t first) -{ - return Array$slice(array, first, I_small(-1)); -} - -public Array_t Array$to(Array_t array, Int_t last) -{ - return Array$slice(array, I_small(1), last); -} - -public Array_t Array$by(Array_t array, Int_t int_stride, int64_t padded_item_size) -{ - int64_t stride = Int64$from_int(int_stride, false); - // In the unlikely event that the stride value would be too large to fit in - // a 15-bit integer, fall back to creating a copy of the array: - if (unlikely(array.stride*stride < ARRAY_MIN_STRIDE || array.stride*stride > ARRAY_MAX_STRIDE)) { - void *copy = NULL; - int64_t len = (stride < 0 ? array.length / -stride : array.length / stride) + ((array.length % stride) != 0); - if (len > 0) { - copy = array.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size)) : GC_MALLOC((size_t)(len * padded_item_size)); - void *start = (stride < 0 ? array.data + (array.stride * (array.length - 1)) : array.data); - for (int64_t i = 0; i < len; i++) - memcpy(copy + i*padded_item_size, start + array.stride*stride*i, (size_t)padded_item_size); - } - return (Array_t){ - .data=copy, - .length=len, - .stride=padded_item_size, - .atomic=array.atomic, - }; - } - - if (stride == 0) - return (Array_t){.atomic=array.atomic}; - - return (Array_t){ - .atomic=array.atomic, - .data=(stride < 0 ? array.data + (array.stride * (array.length - 1)) : array.data), - .length=(stride < 0 ? array.length / -stride : array.length / stride) + ((array.length % stride) != 0), - .stride=array.stride * stride, - .data_refcount=array.data_refcount, - }; -} - -public Array_t Array$slice(Array_t array, Int_t int_first, Int_t int_last) - -{ - int64_t first = Int64$from_int(int_first, false); - if (first < 0) - first = array.length + first + 1; - - int64_t last = Int64$from_int(int_last, false); - if (last < 0) - last = array.length + last + 1; - - if (last > array.length) - last = array.length; - - if (first < 1 || first > array.length || last == 0) - return (Array_t){.atomic=array.atomic}; - - return (Array_t){ - .atomic=array.atomic, - .data=array.data + array.stride*(first-1), - .length=last - first + 1, - .stride=array.stride, - .data_refcount=array.data_refcount, - }; -} - -public Array_t Array$reversed(Array_t array, int64_t padded_item_size) -{ - // Just in case negating the stride gives a value that doesn't fit into a - // 15-bit integer, fall back to Array$by()'s more general method of copying - // the array. This should only happen if array.stride is MIN_STRIDE to - // begin with (very unlikely). - if (unlikely(-array.stride < ARRAY_MIN_STRIDE || -array.stride > ARRAY_MAX_STRIDE)) - return Array$by(array, I(-1), padded_item_size); - - Array_t reversed = array; - reversed.stride = -array.stride; - reversed.data = array.data + (array.length-1)*array.stride; - return reversed; -} - -public Array_t Array$concat(Array_t x, Array_t y, int64_t padded_item_size) -{ - void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size*(x.length + y.length))) - : GC_MALLOC((size_t)(padded_item_size*(x.length + y.length))); - if (x.stride == padded_item_size) { - memcpy(data, x.data, (size_t)(padded_item_size*x.length)); - } else { - for (int64_t i = 0; i < x.length; i++) - memcpy(data + i*padded_item_size, x.data + i*padded_item_size, (size_t)padded_item_size); - } - - void *dest = data + padded_item_size*x.length; - if (y.stride == padded_item_size) { - memcpy(dest, y.data, (size_t)(padded_item_size*y.length)); - } else { - for (int64_t i = 0; i < y.length; i++) - memcpy(dest + i*padded_item_size, y.data + i*y.stride, (size_t)padded_item_size); - } - - return (Array_t){ - .data=data, - .length=x.length + y.length, - .stride=padded_item_size, - .atomic=x.atomic, - }; -} - -public bool Array$has(Array_t array, void *item, const TypeInfo_t *type) -{ - const TypeInfo_t *item_type = type->ArrayInfo.item; - for (int64_t i = 0; i < array.length; i++) { - if (generic_equal(array.data + i*array.stride, item, item_type)) - return true; - } - return false; -} - -public void Array$clear(Array_t *array) -{ - *array = (Array_t){.data=0, .length=0}; -} - -public int32_t Array$compare(const void *vx, const void *vy, const TypeInfo_t *type) -{ - const Array_t *x = (Array_t*)vx, *y = (Array_t*)vy; - // Early out for arrays with the same data, e.g. two copies of the same array: - if (x->data == y->data && x->stride == y->stride) - return (x->length > y->length) - (x->length < y->length); - - const TypeInfo_t *item = type->ArrayInfo.item; - if (item->tag == PointerInfo || !item->metamethods.compare) { // data comparison - int64_t item_padded_size = type->ArrayInfo.item->size; - if (type->ArrayInfo.item->align > 1 && item_padded_size % type->ArrayInfo.item->align) - errx(1, "Item size is not padded!"); - - if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size && item->size == item_padded_size) { - int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length)*item_padded_size)); - if (cmp != 0) return cmp; - } else { - for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) { - int32_t cmp = (int32_t)memcmp(x->data+ x->stride*i, y->data + y->stride*i, (size_t)(item->size)); - if (cmp != 0) return cmp; - } - } - } else { - for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) { - int32_t cmp = generic_compare(x->data + x->stride*i, y->data + y->stride*i, item); - if (cmp != 0) return cmp; - } - } - return (x->length > y->length) - (x->length < y->length); -} - -public bool Array$equal(const void *x, const void *y, const TypeInfo_t *type) -{ - return x == y || (((Array_t*)x)->length == ((Array_t*)y)->length && Array$compare(x, y, type) == 0); -} - -public Text_t Array$as_text(const void *obj, bool colorize, const TypeInfo_t *type) -{ - Array_t *arr = (Array_t*)obj; - if (!arr) - return Text$concat(Text("["), generic_as_text(NULL, false, type->ArrayInfo.item), Text("]")); - - const TypeInfo_t *item_type = type->ArrayInfo.item; - Text_t text = Text("["); - for (int64_t i = 0; i < arr->length; i++) { - if (i > 0) - text = Text$concat(text, Text(", ")); - Text_t item_text = generic_as_text(arr->data + i*arr->stride, colorize, item_type); - text = Text$concat(text, item_text); - } - text = Text$concat(text, Text("]")); - return text; -} - -public uint64_t Array$hash(const void *obj, const TypeInfo_t *type) -{ - const Array_t *arr = (Array_t*)obj; - const TypeInfo_t *item = type->ArrayInfo.item; - siphash sh; - siphashinit(&sh, sizeof(uint64_t[arr->length])); - if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void*))) { // Raw data hash - for (int64_t i = 0; i < arr->length; i++) - siphashadd64bits(&sh, (uint64_t)(arr->data + i*arr->stride)); - } else { - for (int64_t i = 0; i < arr->length; i++) { - uint64_t item_hash = generic_hash(arr->data + i*arr->stride, item); - siphashadd64bits(&sh, item_hash); - } - } - return siphashfinish_last_part(&sh, 0); -} - -static void siftdown(Array_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size) -{ - assert(pos > 0 && pos < heap->length); - char newitem[padded_item_size]; - memcpy(newitem, heap->data + heap->stride*pos, (size_t)(padded_item_size)); - while (pos > startpos) { - int64_t parentpos = (pos - 1) >> 1; - typedef int32_t (*cmp_fn_t)(void*, void*, void*); - int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride*parentpos, comparison.userdata); - if (cmp >= 0) - break; - - memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*parentpos, (size_t)(padded_item_size)); - pos = parentpos; - } - memcpy(heap->data + heap->stride*pos, newitem, (size_t)(padded_item_size)); -} - -static void siftup(Array_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size) -{ - int64_t endpos = heap->length; - int64_t startpos = pos; - assert(pos < endpos); - - char old_top[padded_item_size]; - memcpy(old_top, heap->data + heap->stride*pos, (size_t)(padded_item_size)); - // Bubble up the smallest leaf node - int64_t limit = endpos >> 1; - while (pos < limit) { - int64_t childpos = 2*pos + 1; // Smaller of the two child nodes - if (childpos + 1 < endpos) { - typedef int32_t (*cmp_fn_t)(void*, void*, void*); - int32_t cmp = ((cmp_fn_t)comparison.fn)( - heap->data + heap->stride*childpos, - heap->data + heap->stride*(childpos + 1), - comparison.userdata); - childpos += (cmp >= 0); - } - - // Move the child node up: - memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*childpos, (size_t)(padded_item_size)); - pos = childpos; - } - memcpy(heap->data + heap->stride*pos, old_top, (size_t)(padded_item_size)); - // Shift the node's parents down: - siftdown(heap, startpos, pos, comparison, padded_item_size); -} - -public void Array$heap_push(Array_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size) -{ - Array$insert(heap, item, I(0), padded_item_size); - - if (heap->length > 1) { - if (heap->data_refcount != 0) - Array$compact(heap, padded_item_size); - siftdown(heap, 0, heap->length-1, comparison, padded_item_size); - } -} - -public void Array$heap_pop(Array_t *heap, Closure_t comparison, int64_t padded_item_size) -{ - if (heap->length == 0) - fail("Attempt to pop from an empty array"); - - if (heap->length == 1) { - *heap = (Array_t){}; - } else if (heap->length == 2) { - heap->data += heap->stride; - --heap->length; - } else { - if (heap->data_refcount != 0) - Array$compact(heap, padded_item_size); - memcpy(heap->data, heap->data + heap->stride*(heap->length-1), (size_t)(padded_item_size)); - --heap->length; - siftup(heap, 0, comparison, padded_item_size); - } -} - -public void Array$heapify(Array_t *heap, Closure_t comparison, int64_t padded_item_size) -{ - if (heap->data_refcount != 0) - Array$compact(heap, padded_item_size); - - // It's necessary to bump the refcount because the user's comparison - // function could do stuff that modifies the heap's data. - ARRAY_INCREF(*heap); - int64_t i, n = heap->length; - for (i = (n >> 1) - 1 ; i >= 0 ; i--) - siftup(heap, i, comparison, padded_item_size); - ARRAY_DECREF(*heap); -} - -public Int_t Array$binary_search(Array_t array, void *target, Closure_t comparison) -{ - typedef int32_t (*cmp_fn_t)(void*, void*, void*); - int64_t lo = 0, hi = array.length-1; - while (lo <= hi) { - int64_t mid = (lo + hi) / 2; - int32_t cmp = ((cmp_fn_t)comparison.fn)( - array.data + array.stride*mid, target, comparison.userdata); - if (cmp == 0) - return I(mid+1); - else if (cmp < 0) - lo = mid + 1; - else if (cmp > 0) - hi = mid - 1; - } - return I(lo+1); // Return the index where the target would be inserted -} - -public PUREFUNC bool Array$is_none(const void *obj, const TypeInfo_t*) -{ - return ((Array_t*)obj)->length < 0; -} - -public void Array$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type) -{ - Array_t arr = *(Array_t*)obj; - int64_t len = arr.length; - Int64$serialize(&len, out, pointers, &Int64$info); - auto item_serialize = type->ArrayInfo.item->metamethods.serialize; - if (item_serialize) { - for (int64_t i = 0; i < len; i++) - item_serialize(arr.data + i*arr.stride, out, pointers, type->ArrayInfo.item); - } else if (arr.stride == type->ArrayInfo.item->size) { - fwrite(arr.data, (size_t)type->ArrayInfo.item->size, (size_t)len, out); - } else { - for (int64_t i = 0; i < len; i++) - fwrite(arr.data + i*arr.stride, (size_t)type->ArrayInfo.item->size, 1, out); - } -} - -public void Array$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type) -{ - int64_t len = -1; - Int64$deserialize(in, &len, pointers, &Int64$info); - int64_t padded_size = type->ArrayInfo.item->size; - if (type->ArrayInfo.item->align > 0 && padded_size % type->ArrayInfo.item->align > 0) - padded_size += type->ArrayInfo.item->align - (padded_size % type->ArrayInfo.item->align); - Array_t arr = { - .length=len, - .data=GC_MALLOC((size_t)(len*padded_size)), - .stride=padded_size, - }; - auto item_deserialize = type->ArrayInfo.item->metamethods.deserialize; - if (item_deserialize) { - for (int64_t i = 0; i < len; i++) - item_deserialize(in, arr.data + i*arr.stride, pointers, type->ArrayInfo.item); - } else if (arr.stride == type->ArrayInfo.item->size) { - fread(arr.data, (size_t)type->ArrayInfo.item->size, (size_t)len, in); - } else { - for (int64_t i = 0; i < len; i++) - fread(arr.data + i*arr.stride, (size_t)type->ArrayInfo.item->size, 1, in); - } - *(Array_t*)obj = arr; -} - -// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0 diff --git a/src/stdlib/arrays.h b/src/stdlib/arrays.h deleted file mode 100644 index 9f5f3d00..00000000 --- a/src/stdlib/arrays.h +++ /dev/null @@ -1,137 +0,0 @@ -#pragma once - -// Functions that operate on arrays - -#include - -#include "datatypes.h" -#include "integers.h" -#include "types.h" -#include "util.h" - -// Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1 -#define Array_get(item_type, arr_expr, index_expr, start, end) *({ \ - const Array_t arr = arr_expr; int64_t index = index_expr; \ - int64_t off = index + (index < 0) * (arr.length + 1) - 1; \ - if (unlikely(off < 0 || off >= arr.length)) \ - fail_source(__SOURCE_FILE__, start, end, "Invalid array index: ", index, " (array has length ", (int64_t)arr.length, ")\n"); \ - (item_type*)(arr.data + arr.stride * off);}) -#define Array_get_unchecked(type, x, i) *({ const Array_t arr = x; int64_t index = i; \ - int64_t off = index + (index < 0) * (arr.length + 1) - 1; \ - (type*)(arr.data + arr.stride * off);}) -#define Array_lvalue(item_type, arr_expr, index_expr, start, end) *({ \ - Array_t *arr = arr_expr; int64_t index = index_expr; \ - int64_t off = index + (index < 0) * (arr->length + 1) - 1; \ - if (unlikely(off < 0 || off >= arr->length)) \ - fail_source(__SOURCE_FILE__, start, end, "Invalid array index: ", index, " (array has length ", (int64_t)arr->length, ")\n"); \ - if (arr->data_refcount > 0) \ - Array$compact(arr, sizeof(item_type)); \ - (item_type*)(arr->data + arr->stride * off); }) -#define Array_lvalue_unchecked(item_type, arr_expr, index_expr) *({ \ - Array_t *arr = arr_expr; int64_t index = index_expr; \ - int64_t off = index + (index < 0) * (arr->length + 1) - 1; \ - if (arr->data_refcount > 0) \ - Array$compact(arr, sizeof(item_type)); \ - (item_type*)(arr->data + arr->stride * off); }) -#define Array_set(item_type, arr, index, value, start, end) \ - Array_lvalue(item_type, arr_expr, index, start, end) = value -#define is_atomic(x) _Generic(x, bool: true, int8_t: true, int16_t: true, int32_t: true, int64_t: true, float: true, double: true, default: false) -#define TypedArray(t, ...) ({ t items[] = {__VA_ARGS__}; \ - (Array_t){.length=sizeof(items)/sizeof(items[0]), \ - .stride=(int64_t)&items[1] - (int64_t)&items[0], \ - .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \ - .atomic=0, \ - .data_refcount=0}; }) -#define TypedArrayN(t, N, ...) ({ t items[N] = {__VA_ARGS__}; \ - (Array_t){.length=N, \ - .stride=(int64_t)&items[1] - (int64_t)&items[0], \ - .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \ - .atomic=0, \ - .data_refcount=0}; }) -#define Array(x, ...) ({ __typeof(x) items[] = {x, __VA_ARGS__}; \ - (Array_t){.length=sizeof(items)/sizeof(items[0]), \ - .stride=(int64_t)&items[1] - (int64_t)&items[0], \ - .data=memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items, sizeof(items)), \ - .atomic=is_atomic(x), \ - .data_refcount=0}; }) -// Array refcounts use a saturating add, where once it's at the max value, it stays there. -#define ARRAY_INCREF(arr) (arr).data_refcount += ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT) -#define ARRAY_DECREF(arr) (arr).data_refcount -= ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT) -#define ARRAY_COPY(arr) ({ ARRAY_INCREF(arr); arr; }) - -#define Array$insert_value(arr, item_expr, index, padded_item_size) Array$insert(arr, (__typeof(item_expr)[1]){item_expr}, index, padded_item_size) -void Array$insert(Array_t *arr, const void *item, Int_t index, int64_t padded_item_size); -void Array$insert_all(Array_t *arr, Array_t to_insert, Int_t index, int64_t padded_item_size); -void Array$remove_at(Array_t *arr, Int_t index, Int_t count, int64_t padded_item_size); -void Array$remove_item(Array_t *arr, void *item, Int_t max_removals, const TypeInfo_t *type); -#define Array$remove_item_value(arr, item_expr, max, type) Array$remove_item(arr, (__typeof(item_expr)[1]){item_expr}, max, type) - -#define Array$pop(arr_expr, index_expr, item_type, nonnone_var, nonnone_expr, none_expr) ({ \ - Array_t *arr = arr_expr; \ - Int_t index = index_expr; \ - int64_t index64 = Int64$from_int(index, false); \ - int64_t off = index64 + (index64 < 0) * (arr->length + 1) - 1; \ - (off >= 0 && off < arr->length) ? ({ \ - item_type nonnone_var = *(item_type*)(arr->data + off*arr->stride); \ - Array$remove_at(arr, index, I_small(1), sizeof(item_type)); \ - nonnone_expr; \ - }) : none_expr; }) - -OptionalInt_t Array$find(Array_t arr, void *item, const TypeInfo_t *type); -#define Array$find_value(arr, item_expr, type) ({ __typeof(item_expr) item = item_expr; Array$find(arr, &item, type); }) -OptionalInt_t Array$first(Array_t arr, Closure_t predicate); -void Array$sort(Array_t *arr, Closure_t comparison, int64_t padded_item_size); -Array_t Array$sorted(Array_t arr, Closure_t comparison, int64_t padded_item_size); -void Array$shuffle(Array_t *arr, OptionalClosure_t random_int64, int64_t padded_item_size); -Array_t Array$shuffled(Array_t arr, OptionalClosure_t random_int64, int64_t padded_item_size); -void *Array$random(Array_t arr, OptionalClosure_t random_int64); -#define Array$random_value(arr, random_int64, t) ({ Array_t _arr = arr; if (_arr.length == 0) fail("Cannot get a random value from an empty array!"); *(t*)Array$random(_arr, random_int64); }) -Array_t Array$sample(Array_t arr, Int_t n, Array_t weights, Closure_t random_num, int64_t padded_item_size); -Table_t Array$counts(Array_t arr, const TypeInfo_t *type); -void Array$clear(Array_t *array); -void Array$compact(Array_t *arr, int64_t padded_item_size); -PUREFUNC bool Array$has(Array_t array, void *item, const TypeInfo_t *type); -#define Array$has_value(arr, item_expr, type) ({ __typeof(item_expr) item = item_expr; Array$has(arr, &item, type); }) -PUREFUNC Array_t Array$from(Array_t array, Int_t first); -PUREFUNC Array_t Array$to(Array_t array, Int_t last); -PUREFUNC Array_t Array$by(Array_t array, Int_t stride, int64_t padded_item_size); -PUREFUNC Array_t Array$slice(Array_t array, Int_t int_first, Int_t int_last); -PUREFUNC Array_t Array$reversed(Array_t array, int64_t padded_item_size); -Array_t Array$concat(Array_t x, Array_t y, int64_t padded_item_size); -PUREFUNC uint64_t Array$hash(const void *arr, const TypeInfo_t *type); -PUREFUNC int32_t Array$compare(const void *x, const void *y, const TypeInfo_t *type); -PUREFUNC bool Array$equal(const void *x, const void *y, const TypeInfo_t *type); -PUREFUNC bool Array$is_none(const void *obj, const TypeInfo_t*); -Text_t Array$as_text(const void *arr, bool colorize, const TypeInfo_t *type); -void Array$heapify(Array_t *heap, Closure_t comparison, int64_t padded_item_size); -void Array$heap_push(Array_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size); -#define Array$heap_push_value(heap, _value, comparison, padded_item_size) ({ __typeof(_value) value = _value; Array$heap_push(heap, &value, comparison, padded_item_size); }) -void Array$heap_pop(Array_t *heap, Closure_t comparison, int64_t padded_item_size); -#define Array$heap_pop_value(heap, comparison, type, nonnone_var, nonnone_expr, none_expr) \ - ({ Array_t *_heap = heap; \ - (_heap->length > 0) ? ({ \ - type nonnone_var = *(type*)_heap->data; \ - Array$heap_pop(_heap, comparison, sizeof(type)); \ - nonnone_expr; \ - }) : none_expr; }) -Int_t Array$binary_search(Array_t array, void *target, Closure_t comparison); -#define Array$binary_search_value(array, target, comparison) \ - ({ __typeof(target) _target = target; Array$binary_search(array, &_target, comparison); }) -void Array$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Array$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type); - -#define Array$metamethods { \ - .as_text=Array$as_text, \ - .compare=Array$compare, \ - .equal=Array$equal, \ - .hash=Array$hash, \ - .is_none=Array$is_none, \ - .serialize=Array$serialize, \ - .deserialize=Array$deserialize, \ -} - -#define Array$info(item_info) &((TypeInfo_t){.size=sizeof(Array_t), .align=__alignof__(Array_t), \ - .tag=ArrayInfo, .ArrayInfo.item=item_info, \ - .metamethods=Array$metamethods}) - -// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0 diff --git a/src/stdlib/c_strings.c b/src/stdlib/c_strings.c index 9d0f2819..dc777a7c 100644 --- a/src/stdlib/c_strings.c +++ b/src/stdlib/c_strings.c @@ -59,7 +59,7 @@ static void CString$serialize(const void *obj, FILE *out, Table_t *pointers, con fwrite(str, sizeof(char), (size_t)len, out); } -static void CString$deserialize(FILE *in, void *out, Array_t *pointers, const TypeInfo_t *) +static void CString$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *) { int64_t len = -1; Int64$deserialize(in, &len, pointers, &Int64$info); diff --git a/src/stdlib/datatypes.h b/src/stdlib/datatypes.h index 6f3b7676..950c9457 100644 --- a/src/stdlib/datatypes.h +++ b/src/stdlib/datatypes.h @@ -1,22 +1,22 @@ #pragma once -// Common datastructures (arrays, tables, closures) +// Common datastructures (lists, tables, closures) #include #include #include #include -#define ARRAY_LENGTH_BITS 42 -#define ARRAY_FREE_BITS 6 -#define ARRAY_REFCOUNT_BITS 3 -#define ARRAY_STRIDE_BITS 12 +#define LIST_LENGTH_BITS 42 +#define LIST_FREE_BITS 6 +#define LIST_REFCOUNT_BITS 3 +#define LIST_STRIDE_BITS 12 #define MAX_FOR_N_BITS(N) ((1<<(N))-1) -#define ARRAY_MAX_STRIDE MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1) -#define ARRAY_MIN_STRIDE (~MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1)) -#define ARRAY_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(ARRAY_REFCOUNT_BITS) -#define ARRAY_MAX_FREE_ENTRIES MAX_FOR_N_BITS(ARRAY_FREE_BITS) +#define LIST_MAX_STRIDE MAX_FOR_N_BITS(LIST_STRIDE_BITS-1) +#define LIST_MIN_STRIDE (~MAX_FOR_N_BITS(LIST_STRIDE_BITS-1)) +#define LIST_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(LIST_REFCOUNT_BITS) +#define LIST_MAX_FREE_ENTRIES MAX_FOR_N_BITS(LIST_FREE_BITS) #define Num_t double #define Num32_t float @@ -37,16 +37,16 @@ typedef union { typedef struct { void *data; - // All of the following fields add up to 64 bits, which means that array + // All of the following fields add up to 64 bits, which means that list // structs can be passed in two 64-bit registers. C will handle doing the // bit arithmetic to extract the necessary values, which is cheaper than // spilling onto the stack and needing to retrieve data from the stack. - int64_t length:ARRAY_LENGTH_BITS; - uint8_t free:ARRAY_FREE_BITS; + int64_t length:LIST_LENGTH_BITS; + uint8_t free:LIST_FREE_BITS; bool atomic:1; - uint8_t data_refcount:ARRAY_REFCOUNT_BITS; - int16_t stride:ARRAY_STRIDE_BITS; -} Array_t; + uint8_t data_refcount:LIST_REFCOUNT_BITS; + int16_t stride:LIST_STRIDE_BITS; +} List_t; typedef struct { uint32_t occupied:1, index:31; @@ -63,7 +63,7 @@ typedef struct { } bucket_info_t; typedef struct table_s { - Array_t entries; + List_t entries; uint64_t hash; bucket_info_t *bucket_info; struct table_s *fallback; @@ -101,12 +101,12 @@ typedef struct { typedef struct { PathType_t type; - Array_t components; + List_t components; } Path_t; #define OptionalPath_t Path_t #define OptionalBool_t uint8_t -#define OptionalArray_t Array_t +#define OptionalList_t List_t #define OptionalTable_t Table_t #define OptionalText_t Text_t #define OptionalClosure_t Closure_t diff --git a/src/stdlib/enums.c b/src/stdlib/enums.c index b66a1711..bcf47d8e 100644 --- a/src/stdlib/enums.c +++ b/src/stdlib/enums.c @@ -3,7 +3,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "bools.h" #include "functiontype.h" #include "integers.h" @@ -102,7 +102,7 @@ public void Enum$serialize(const void *obj, FILE *out, Table_t *pointers, const } } -public void Enum$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void Enum$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type) { int32_t tag = 0; Int32$deserialize(in, &tag, pointers, &Int32$info); diff --git a/src/stdlib/enums.h b/src/stdlib/enums.h index b5427711..8345c527 100644 --- a/src/stdlib/enums.h +++ b/src/stdlib/enums.h @@ -13,7 +13,7 @@ PUREFUNC bool Enum$equal(const void *x, const void *y, const TypeInfo_t *type); PUREFUNC Text_t Enum$as_text(const void *obj, bool colorize, const TypeInfo_t *type); PUREFUNC bool Enum$is_none(const void *obj, const TypeInfo_t *type); void Enum$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Enum$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type); +void Enum$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type); #define Enum$metamethods { \ .as_text=Enum$as_text, \ diff --git a/src/stdlib/integers.c b/src/stdlib/integers.c index 8086239d..7943caee 100644 --- a/src/stdlib/integers.c +++ b/src/stdlib/integers.c @@ -9,7 +9,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "datatypes.h" #include "integers.h" #include "optionals.h" @@ -480,7 +480,7 @@ static void Int$serialize(const void *obj, FILE *out, Table_t *pointers, const T } } -static void Int$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t*) +static void Int$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t*) { if (fgetc(in) == 0) { int64_t i = 0; @@ -519,7 +519,7 @@ public void Int64$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo fputc((uint8_t)z, out); } -public void Int64$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*) +public void Int64$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*) { uint64_t z = 0; for(size_t shift = 0; ; shift += 7) { @@ -541,7 +541,7 @@ public void Int32$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo fputc((uint8_t)z, out); } -public void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*) +public void Int32$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*) { uint32_t z = 0; for(size_t shift = 0; ; shift += 7) { @@ -580,14 +580,14 @@ public void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t Int_t as_int = Int$from_int64((int64_t)i); \ return Int$octal(as_int, digits_int, prefix); \ } \ - public Array_t KindOfInt ## $bits(c_type x) { \ - Array_t bit_array = (Array_t){.data=GC_MALLOC_ATOMIC(sizeof(bool[8*sizeof(c_type)])), .atomic=1, .stride=sizeof(bool), .length=8*sizeof(c_type)}; \ - bool *bits = bit_array.data + sizeof(c_type)*8; \ + public List_t KindOfInt ## $bits(c_type x) { \ + List_t bit_list = (List_t){.data=GC_MALLOC_ATOMIC(sizeof(bool[8*sizeof(c_type)])), .atomic=1, .stride=sizeof(bool), .length=8*sizeof(c_type)}; \ + bool *bits = bit_list.data + sizeof(c_type)*8; \ for (size_t i = 0; i < 8*sizeof(c_type); i++) { \ *(bits--) = x & 1; \ x >>= 1; \ } \ - return bit_array; \ + return bit_list; \ } \ typedef struct { \ Optional##KindOfInt##_t current, last; \ diff --git a/src/stdlib/integers.h b/src/stdlib/integers.h index 43fc2217..8988e7c8 100644 --- a/src/stdlib/integers.h +++ b/src/stdlib/integers.h @@ -29,7 +29,7 @@ Text_t type_name ## $format(c_type i, Int_t digits); \ Text_t type_name ## $hex(c_type i, Int_t digits, bool uppercase, bool prefix); \ Text_t type_name ## $octal(c_type i, Int_t digits, bool prefix); \ - Array_t type_name ## $bits(c_type x); \ + List_t type_name ## $bits(c_type x); \ Closure_t type_name ## $to(c_type first, c_type last, Optional ## type_name ## _t step); \ Closure_t type_name ## $onward(c_type first, c_type step); \ PUREFUNC Optional ## type_name ## _t type_name ## $parse(Text_t text); \ @@ -84,9 +84,9 @@ DEFINE_INT_TYPE(int8_t, Int8) #define Int8$abs(...) I8(abs(__VA_ARGS__)) void Int64$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo_t*); -void Int64$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*); +void Int64$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*); void Int32$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo_t*); -void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*); +void Int32$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*); Text_t Int$as_text(const void *i, bool colorize, const TypeInfo_t *type); Text_t Int$value_as_text(Int_t i); diff --git a/src/stdlib/lists.c b/src/stdlib/lists.c new file mode 100644 index 00000000..69ac7026 --- /dev/null +++ b/src/stdlib/lists.c @@ -0,0 +1,813 @@ +// Functions that operate on lists + +#include +#include +#include +#include + +#include "lists.h" +#include "integers.h" +#include "math.h" +#include "metamethods.h" +#include "optionals.h" +#include "tables.h" +#include "text.h" +#include "util.h" + +// Use inline version of siphash code: +#include "siphash.h" +#include "siphash-internals.h" + +PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info) +{ + int64_t size = info->ListInfo.item->size; + if (info->ListInfo.item->align > 1 && size % info->ListInfo.item->align) + errx(1, "Item size is not padded!"); + return size; +} + +// Replace the list's .data pointer with a new pointer to a copy of the +// data that is compacted and has a stride of exactly `padded_item_size` +public void List$compact(List_t *list, int64_t padded_item_size) +{ + void *copy = NULL; + if (list->length > 0) { + copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->length * (size_t)padded_item_size) + : GC_MALLOC((size_t)list->length * (size_t)padded_item_size); + if ((int64_t)list->stride == padded_item_size) { + memcpy(copy, list->data, (size_t)list->length * (size_t)padded_item_size); + } else { + for (int64_t i = 0; i < list->length; i++) + memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size); + } + } + *list = (List_t){ + .data=copy, + .length=list->length, + .stride=padded_item_size, + .atomic=list->atomic, + }; +} + +public void List$insert(List_t *list, const void *item, Int_t int_index, int64_t padded_item_size) +{ + int64_t index = Int64$from_int(int_index, false); + if (index <= 0) index = list->length + index + 1; + + if (index < 1) index = 1; + else if (index > (int64_t)list->length + 1) + fail("Invalid insertion index ", index, " for a list with length ", (int64_t)list->length); + + if (!list->data) { + list->free = 4; + list->data = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->free * (size_t)padded_item_size) + : GC_MALLOC((size_t)list->free * (size_t)padded_item_size); + list->stride = padded_item_size; + } else if (list->free < 1 || list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) { + // Resize policy: +50% growth (clamped between 8 and LIST_MAX_FREE_ENTRIES) + list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, list->length)/2); + void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)(list->length + list->free) * (size_t)padded_item_size) + : GC_MALLOC((size_t)(list->length + list->free) * (size_t)padded_item_size); + for (int64_t i = 0; i < index-1; i++) + memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size); + for (int64_t i = index-1; i < (int64_t)list->length; i++) + memcpy(copy + (i+1)*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size); + list->data = copy; + list->data_refcount = 0; + list->stride = padded_item_size; + } else { + if (index != list->length+1) + memmove( + list->data + index*padded_item_size, + list->data + (index-1)*padded_item_size, + (size_t)((list->length - index + 1)*padded_item_size)); + } + assert(list->free > 0); + --list->free; + ++list->length; + memcpy((void*)list->data + (index-1)*padded_item_size, item, (size_t)padded_item_size); +} + +public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int64_t padded_item_size) +{ + int64_t index = Int64$from_int(int_index, false); + if (to_insert.length == 0) + return; + + if (!list->data) { + *list = to_insert; + LIST_INCREF(*list); + return; + } + + if (index < 1) index = list->length + index + 1; + + if (index < 1) index = 1; + else if (index > (int64_t)list->length + 1) + fail("Invalid insertion index ", index, " for a list with length ", (int64_t)list->length); + + if ((int64_t)list->free >= (int64_t)to_insert.length // Adequate free space + && list->data_refcount == 0 // Not aliased memory + && (int64_t)list->stride == padded_item_size) { // Contiguous list + // If we can fit this within the list's preallocated free space, do that: + list->free -= to_insert.length; + list->length += to_insert.length; + if (index != list->length+1) + memmove((void*)list->data + index*padded_item_size, + list->data + (index-1)*padded_item_size, + (size_t)((list->length - index + to_insert.length-1)*padded_item_size)); + for (int64_t i = 0; i < to_insert.length; i++) + memcpy((void*)list->data + (index-1 + i)*padded_item_size, + to_insert.data + i*to_insert.stride, (size_t)padded_item_size); + } else { + // Otherwise, allocate a new chunk of memory for the list and populate it: + int64_t new_len = list->length + to_insert.length; + list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, new_len/4)); + void *data = list->atomic ? GC_MALLOC_ATOMIC((size_t)((new_len + list->free) * padded_item_size)) + : GC_MALLOC((size_t)((new_len + list->free) * padded_item_size)); + void *p = data; + + // Copy first chunk of `list` if needed: + if (index > 1) { + if (list->stride == padded_item_size) { + memcpy(p, list->data, (size_t)((index-1)*padded_item_size)); + p += (index-1)*padded_item_size; + } else { + for (int64_t i = 0; i < index-1; i++) { + memcpy(p, list->data + list->stride*i, (size_t)padded_item_size); + p += padded_item_size; + } + } + } + + // Copy `to_insert` + if (to_insert.stride == padded_item_size) { + memcpy(p, to_insert.data, (size_t)(to_insert.length*padded_item_size)); + p += to_insert.length*padded_item_size; + } else { + for (int64_t i = 0; i < index-1; i++) { + memcpy(p, to_insert.data + to_insert.stride*i, (size_t)padded_item_size); + p += padded_item_size; + } + } + + // Copy last chunk of `list` if needed: + if (index < list->length + 1) { + if (list->stride == padded_item_size) { + memcpy(p, list->data + padded_item_size*(index-1), (size_t)((list->length - index + 1)*padded_item_size)); + p += (list->length - index + 1)*padded_item_size; + } else { + for (int64_t i = index-1; i < list->length-1; i++) { + memcpy(p, list->data + list->stride*i, (size_t)padded_item_size); + p += padded_item_size; + } + } + } + list->length = new_len; + list->stride = padded_item_size; + list->data = data; + list->data_refcount = 0; + } +} + +public void List$remove_at(List_t *list, Int_t int_index, Int_t int_count, int64_t padded_item_size) +{ + int64_t index = Int64$from_int(int_index, false); + if (index < 1) index = list->length + index + 1; + + int64_t count = Int64$from_int(int_count, false); + if (index < 1 || index > (int64_t)list->length || count < 1) return; + + if (count > list->length - index + 1) + count = (list->length - index) + 1; + + if (index == 1) { + list->data += list->stride * count; + } else if (index + count > list->length) { + list->free += count; + } else if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) { + void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)((list->length-1) * padded_item_size)) + : GC_MALLOC((size_t)((list->length-1) * padded_item_size)); + for (int64_t src = 1, dest = 1; src <= (int64_t)list->length; src++) { + if (src < index || src >= index + count) { + memcpy(copy + (dest - 1)*padded_item_size, list->data + list->stride*(src - 1), (size_t)padded_item_size); + ++dest; + } + } + list->data = copy; + list->free = 0; + list->data_refcount = 0; + } else { + memmove((void*)list->data + (index-1)*padded_item_size, list->data + (index-1 + count)*padded_item_size, + (size_t)((list->length - index + count - 1)*padded_item_size)); + list->free += count; + } + list->length -= count; + if (list->length == 0) list->data = NULL; +} + +public void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type) +{ + int64_t padded_item_size = get_padded_item_size(type); + const Int_t ZERO = (Int_t){.small=(0<<2)|1}; + const Int_t ONE = (Int_t){.small=(1<<2)|1}; + const TypeInfo_t *item_type = type->ListInfo.item; + for (int64_t i = 0; i < list->length; ) { + if (max_removals.small == ZERO.small) // zero + break; + + if (generic_equal(item, list->data + i*list->stride, item_type)) { + List$remove_at(list, I(i+1), ONE, padded_item_size); + max_removals = Int$minus(max_removals, ONE); + } else { + i++; + } + } +} + +public OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type) +{ + const TypeInfo_t *item_type = type->ListInfo.item; + for (int64_t i = 0; i < list.length; i++) { + if (generic_equal(item, list.data + i*list.stride, item_type)) + return I(i+1); + } + return NONE_INT; +} + +public OptionalInt_t List$first(List_t list, Closure_t predicate) +{ + bool (*is_good)(void*, void*) = (void*)predicate.fn; + for (int64_t i = 0; i < list.length; i++) { + if (is_good(list.data + i*list.stride, predicate.userdata)) + return I(i+1); + } + return NONE_INT; +} + +static Closure_t _sort_comparison = {.fn=NULL}; + +int _compare_closure(const void *a, const void *b) +{ + typedef int (*comparison_t)(const void*, const void*, void*); + return ((comparison_t)_sort_comparison.fn)(a, b, _sort_comparison.userdata); +} + +public void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size) +{ + if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) + List$compact(list, padded_item_size); + + _sort_comparison = comparison; + qsort(list->data, (size_t)list->length, (size_t)padded_item_size, _compare_closure); +} + +public List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size) +{ + List$compact(&list, padded_item_size); + _sort_comparison = comparison; + qsort(list.data, (size_t)list.length, (size_t)padded_item_size, _compare_closure); + return list; +} + +#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__) +static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) { + (void)flags; + arc4random_buf(buf, buflen); + return buflen; +} +#elif defined(__linux__) +// Use getrandom() +# include +#else + #error "Unsupported platform for secure random number generation" +#endif + +static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata) +{ + (void)userdata; + if (min > max) fail("Random minimum value (", min, ") is larger than the maximum value (", max, ")"); + if (min == max) return min; + uint64_t range = (uint64_t)max - (uint64_t)min + 1; + uint64_t min_r = -range % range; + uint64_t r; + for (;;) { + getrandom(&r, sizeof(r), 0); + if (r >= min_r) break; + } + return (int64_t)((uint64_t)min + (r % range)); +} + +public void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size) +{ + if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) + List$compact(list, padded_item_size); + + typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*); + rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64; + char tmp[padded_item_size]; + for (int64_t i = list->length-1; i > 1; i--) { + int64_t j = rng_fn(0, i, random_int64.userdata); + if unlikely (j < 0 || j > list->length-1) + fail("The provided random number function returned an invalid value: ", j, " (not between 0 and ", i, ")"); + memcpy(tmp, list->data + i*padded_item_size, (size_t)padded_item_size); + memcpy((void*)list->data + i*padded_item_size, list->data + j*padded_item_size, (size_t)padded_item_size); + memcpy((void*)list->data + j*padded_item_size, tmp, (size_t)padded_item_size); + } +} + +public List_t List$shuffled(List_t list, Closure_t random_int64, int64_t padded_item_size) +{ + List$compact(&list, padded_item_size); + List$shuffle(&list, random_int64, padded_item_size); + return list; +} + +public void *List$random(List_t list, OptionalClosure_t random_int64) +{ + if (list.length == 0) + return NULL; // fail("Cannot get a random item from an empty list!"); + + typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*); + rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64; + int64_t index = rng_fn(0, list.length-1, random_int64.userdata); + if unlikely (index < 0 || index > list.length-1) + fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ", (int64_t)list.length, ")"); + return list.data + list.stride*index; +} + +public Table_t List$counts(List_t list, const TypeInfo_t *type) +{ + Table_t counts = {}; + const TypeInfo_t count_type = *Table$info(type->ListInfo.item, &Int$info); + for (int64_t i = 0; i < list.length; i++) { + void *key = list.data + i*list.stride; + int64_t *count = Table$get(counts, key, &count_type); + int64_t val = count ? *count + 1 : 1; + Table$set(&counts, key, &val, &count_type); + } + return counts; +} + +static double _default_random_num(void *userdata) +{ + (void)userdata; + union { + Num_t num; + uint64_t bits; + } r = {.bits=0}, one = {.num=1.0}; + getrandom((uint8_t*)&r, sizeof(r), 0); + + // Set r.num to 1. + r.bits &= ~(0xFFFULL << 52); + r.bits |= (one.bits & (0xFFFULL << 52)); + return r.num - 1.0; +} + +public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClosure_t random_num, int64_t padded_item_size) +{ + int64_t n = Int64$from_int(int_n, false); + if (n < 0) + fail("Cannot select a negative number of values"); + + if (n == 0) + return (List_t){}; + + if (list.length == 0) + fail("There are no elements in this list!"); + + if (weights.length != list.length) + fail("List has ", (int64_t)list.length, " elements, but there are ", (int64_t)weights.length, " weights given"); + + double total = 0.0; + for (int64_t i = 0; i < weights.length && i < list.length; i++) { + double weight = *(double*)(weights.data + weights.stride*i); + if (isinf(weight)) + fail("Infinite weight!"); + else if (isnan(weight)) + fail("NaN weight!"); + else if (weight < 0.0) + fail("Negative weight!"); + else + total += weight; + } + + if (isinf(total)) + fail("Sample weights have overflowed to infinity"); + + if (total == 0.0) + fail("None of the given weights are nonzero"); + + double inverse_average = (double)list.length / total; + + struct { + int64_t alias; + double odds; + } aliases[list.length]; + + for (int64_t i = 0; i < list.length; i++) { + double weight = i >= weights.length ? 0.0 : *(double*)(weights.data + weights.stride*i); + aliases[i].odds = weight * inverse_average; + aliases[i].alias = -1; + } + + int64_t small = 0; + for (int64_t big = 0; big < list.length; big++) { + while (aliases[big].odds >= 1.0) { + while (small < list.length && (aliases[small].odds >= 1.0 || aliases[small].alias != -1)) + ++small; + + if (small >= list.length) { + aliases[big].odds = 1.0; + aliases[big].alias = big; + break; + } + + aliases[small].alias = big; + aliases[big].odds = (aliases[small].odds + aliases[big].odds) - 1.0; + } + if (big < small) small = big; + } + + for (int64_t i = small; i < list.length; i++) + if (aliases[i].alias == -1) + aliases[i].alias = i; + + typedef double (*rng_fn_t)(void*); + rng_fn_t rng_fn = random_num.fn ? (rng_fn_t)random_num.fn : _default_random_num; + + List_t selected = { + .data=list.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size)) : GC_MALLOC((size_t)(n * padded_item_size)), + .length=n, + .stride=padded_item_size, .atomic=list.atomic}; + for (int64_t i = 0; i < n; i++) { + double r = rng_fn(random_num.userdata); + if unlikely (r < 0.0 || r >= 1.0) + fail("The random number function returned a value not between 0.0 (inclusive) and 1.0 (exclusive): ", r); + r *= (double)list.length; + int64_t index = (int64_t)r; + assert(index >= 0 && index < list.length); + if ((r - (double)index) > aliases[index].odds) + index = aliases[index].alias; + memcpy(selected.data + i*selected.stride, list.data + index*list.stride, (size_t)padded_item_size); + } + return selected; +} + +public List_t List$from(List_t list, Int_t first) +{ + return List$slice(list, first, I_small(-1)); +} + +public List_t List$to(List_t list, Int_t last) +{ + return List$slice(list, I_small(1), last); +} + +public List_t List$by(List_t list, Int_t int_stride, int64_t padded_item_size) +{ + int64_t stride = Int64$from_int(int_stride, false); + // In the unlikely event that the stride value would be too large to fit in + // a 15-bit integer, fall back to creating a copy of the list: + if (unlikely(list.stride*stride < LIST_MIN_STRIDE || list.stride*stride > LIST_MAX_STRIDE)) { + void *copy = NULL; + int64_t len = (stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0); + if (len > 0) { + copy = list.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size)) : GC_MALLOC((size_t)(len * padded_item_size)); + void *start = (stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data); + for (int64_t i = 0; i < len; i++) + memcpy(copy + i*padded_item_size, start + list.stride*stride*i, (size_t)padded_item_size); + } + return (List_t){ + .data=copy, + .length=len, + .stride=padded_item_size, + .atomic=list.atomic, + }; + } + + if (stride == 0) + return (List_t){.atomic=list.atomic}; + + return (List_t){ + .atomic=list.atomic, + .data=(stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data), + .length=(stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0), + .stride=list.stride * stride, + .data_refcount=list.data_refcount, + }; +} + +public List_t List$slice(List_t list, Int_t int_first, Int_t int_last) + +{ + int64_t first = Int64$from_int(int_first, false); + if (first < 0) + first = list.length + first + 1; + + int64_t last = Int64$from_int(int_last, false); + if (last < 0) + last = list.length + last + 1; + + if (last > list.length) + last = list.length; + + if (first < 1 || first > list.length || last == 0) + return (List_t){.atomic=list.atomic}; + + return (List_t){ + .atomic=list.atomic, + .data=list.data + list.stride*(first-1), + .length=last - first + 1, + .stride=list.stride, + .data_refcount=list.data_refcount, + }; +} + +public List_t List$reversed(List_t list, int64_t padded_item_size) +{ + // Just in case negating the stride gives a value that doesn't fit into a + // 15-bit integer, fall back to List$by()'s more general method of copying + // the list. This should only happen if list.stride is MIN_STRIDE to + // begin with (very unlikely). + if (unlikely(-list.stride < LIST_MIN_STRIDE || -list.stride > LIST_MAX_STRIDE)) + return List$by(list, I(-1), padded_item_size); + + List_t reversed = list; + reversed.stride = -list.stride; + reversed.data = list.data + (list.length-1)*list.stride; + return reversed; +} + +public List_t List$concat(List_t x, List_t y, int64_t padded_item_size) +{ + void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size*(x.length + y.length))) + : GC_MALLOC((size_t)(padded_item_size*(x.length + y.length))); + if (x.stride == padded_item_size) { + memcpy(data, x.data, (size_t)(padded_item_size*x.length)); + } else { + for (int64_t i = 0; i < x.length; i++) + memcpy(data + i*padded_item_size, x.data + i*padded_item_size, (size_t)padded_item_size); + } + + void *dest = data + padded_item_size*x.length; + if (y.stride == padded_item_size) { + memcpy(dest, y.data, (size_t)(padded_item_size*y.length)); + } else { + for (int64_t i = 0; i < y.length; i++) + memcpy(dest + i*padded_item_size, y.data + i*y.stride, (size_t)padded_item_size); + } + + return (List_t){ + .data=data, + .length=x.length + y.length, + .stride=padded_item_size, + .atomic=x.atomic, + }; +} + +public bool List$has(List_t list, void *item, const TypeInfo_t *type) +{ + const TypeInfo_t *item_type = type->ListInfo.item; + for (int64_t i = 0; i < list.length; i++) { + if (generic_equal(list.data + i*list.stride, item, item_type)) + return true; + } + return false; +} + +public void List$clear(List_t *list) +{ + *list = (List_t){.data=0, .length=0}; +} + +public int32_t List$compare(const void *vx, const void *vy, const TypeInfo_t *type) +{ + const List_t *x = (List_t*)vx, *y = (List_t*)vy; + // Early out for lists with the same data, e.g. two copies of the same list: + if (x->data == y->data && x->stride == y->stride) + return (x->length > y->length) - (x->length < y->length); + + const TypeInfo_t *item = type->ListInfo.item; + if (item->tag == PointerInfo || !item->metamethods.compare) { // data comparison + int64_t item_padded_size = type->ListInfo.item->size; + if (type->ListInfo.item->align > 1 && item_padded_size % type->ListInfo.item->align) + errx(1, "Item size is not padded!"); + + if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size && item->size == item_padded_size) { + int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length)*item_padded_size)); + if (cmp != 0) return cmp; + } else { + for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) { + int32_t cmp = (int32_t)memcmp(x->data+ x->stride*i, y->data + y->stride*i, (size_t)(item->size)); + if (cmp != 0) return cmp; + } + } + } else { + for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) { + int32_t cmp = generic_compare(x->data + x->stride*i, y->data + y->stride*i, item); + if (cmp != 0) return cmp; + } + } + return (x->length > y->length) - (x->length < y->length); +} + +public bool List$equal(const void *x, const void *y, const TypeInfo_t *type) +{ + return x == y || (((List_t*)x)->length == ((List_t*)y)->length && List$compare(x, y, type) == 0); +} + +public Text_t List$as_text(const void *obj, bool colorize, const TypeInfo_t *type) +{ + List_t *list = (List_t*)obj; + if (!list) + return Text$concat(Text("["), generic_as_text(NULL, false, type->ListInfo.item), Text("]")); + + const TypeInfo_t *item_type = type->ListInfo.item; + Text_t text = Text("["); + for (int64_t i = 0; i < list->length; i++) { + if (i > 0) + text = Text$concat(text, Text(", ")); + Text_t item_text = generic_as_text(list->data + i*list->stride, colorize, item_type); + text = Text$concat(text, item_text); + } + text = Text$concat(text, Text("]")); + return text; +} + +public uint64_t List$hash(const void *obj, const TypeInfo_t *type) +{ + const List_t *list = (List_t*)obj; + const TypeInfo_t *item = type->ListInfo.item; + siphash sh; + siphashinit(&sh, sizeof(uint64_t[list->length])); + if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void*))) { // Raw data hash + for (int64_t i = 0; i < list->length; i++) + siphashadd64bits(&sh, (uint64_t)(list->data + i*list->stride)); + } else { + for (int64_t i = 0; i < list->length; i++) { + uint64_t item_hash = generic_hash(list->data + i*list->stride, item); + siphashadd64bits(&sh, item_hash); + } + } + return siphashfinish_last_part(&sh, 0); +} + +static void siftdown(List_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size) +{ + assert(pos > 0 && pos < heap->length); + char newitem[padded_item_size]; + memcpy(newitem, heap->data + heap->stride*pos, (size_t)(padded_item_size)); + while (pos > startpos) { + int64_t parentpos = (pos - 1) >> 1; + typedef int32_t (*cmp_fn_t)(void*, void*, void*); + int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride*parentpos, comparison.userdata); + if (cmp >= 0) + break; + + memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*parentpos, (size_t)(padded_item_size)); + pos = parentpos; + } + memcpy(heap->data + heap->stride*pos, newitem, (size_t)(padded_item_size)); +} + +static void siftup(List_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size) +{ + int64_t endpos = heap->length; + int64_t startpos = pos; + assert(pos < endpos); + + char old_top[padded_item_size]; + memcpy(old_top, heap->data + heap->stride*pos, (size_t)(padded_item_size)); + // Bubble up the smallest leaf node + int64_t limit = endpos >> 1; + while (pos < limit) { + int64_t childpos = 2*pos + 1; // Smaller of the two child nodes + if (childpos + 1 < endpos) { + typedef int32_t (*cmp_fn_t)(void*, void*, void*); + int32_t cmp = ((cmp_fn_t)comparison.fn)( + heap->data + heap->stride*childpos, + heap->data + heap->stride*(childpos + 1), + comparison.userdata); + childpos += (cmp >= 0); + } + + // Move the child node up: + memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*childpos, (size_t)(padded_item_size)); + pos = childpos; + } + memcpy(heap->data + heap->stride*pos, old_top, (size_t)(padded_item_size)); + // Shift the node's parents down: + siftdown(heap, startpos, pos, comparison, padded_item_size); +} + +public void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size) +{ + List$insert(heap, item, I(0), padded_item_size); + + if (heap->length > 1) { + if (heap->data_refcount != 0) + List$compact(heap, padded_item_size); + siftdown(heap, 0, heap->length-1, comparison, padded_item_size); + } +} + +public void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size) +{ + if (heap->length == 0) + fail("Attempt to pop from an empty list"); + + if (heap->length == 1) { + *heap = (List_t){}; + } else if (heap->length == 2) { + heap->data += heap->stride; + --heap->length; + } else { + if (heap->data_refcount != 0) + List$compact(heap, padded_item_size); + memcpy(heap->data, heap->data + heap->stride*(heap->length-1), (size_t)(padded_item_size)); + --heap->length; + siftup(heap, 0, comparison, padded_item_size); + } +} + +public void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size) +{ + if (heap->data_refcount != 0) + List$compact(heap, padded_item_size); + + // It's necessary to bump the refcount because the user's comparison + // function could do stuff that modifies the heap's data. + LIST_INCREF(*heap); + int64_t i, n = heap->length; + for (i = (n >> 1) - 1 ; i >= 0 ; i--) + siftup(heap, i, comparison, padded_item_size); + LIST_DECREF(*heap); +} + +public Int_t List$binary_search(List_t list, void *target, Closure_t comparison) +{ + typedef int32_t (*cmp_fn_t)(void*, void*, void*); + int64_t lo = 0, hi = list.length-1; + while (lo <= hi) { + int64_t mid = (lo + hi) / 2; + int32_t cmp = ((cmp_fn_t)comparison.fn)( + list.data + list.stride*mid, target, comparison.userdata); + if (cmp == 0) + return I(mid+1); + else if (cmp < 0) + lo = mid + 1; + else if (cmp > 0) + hi = mid - 1; + } + return I(lo+1); // Return the index where the target would be inserted +} + +public PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t*) +{ + return ((List_t*)obj)->length < 0; +} + +public void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type) +{ + List_t list = *(List_t*)obj; + int64_t len = list.length; + Int64$serialize(&len, out, pointers, &Int64$info); + auto item_serialize = type->ListInfo.item->metamethods.serialize; + if (item_serialize) { + for (int64_t i = 0; i < len; i++) + item_serialize(list.data + i*list.stride, out, pointers, type->ListInfo.item); + } else if (list.stride == type->ListInfo.item->size) { + fwrite(list.data, (size_t)type->ListInfo.item->size, (size_t)len, out); + } else { + for (int64_t i = 0; i < len; i++) + fwrite(list.data + i*list.stride, (size_t)type->ListInfo.item->size, 1, out); + } +} + +public void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type) +{ + int64_t len = -1; + Int64$deserialize(in, &len, pointers, &Int64$info); + int64_t padded_size = type->ListInfo.item->size; + if (type->ListInfo.item->align > 0 && padded_size % type->ListInfo.item->align > 0) + padded_size += type->ListInfo.item->align - (padded_size % type->ListInfo.item->align); + List_t list = { + .length=len, + .data=GC_MALLOC((size_t)(len*padded_size)), + .stride=padded_size, + }; + auto item_deserialize = type->ListInfo.item->metamethods.deserialize; + if (item_deserialize) { + for (int64_t i = 0; i < len; i++) + item_deserialize(in, list.data + i*list.stride, pointers, type->ListInfo.item); + } else if (list.stride == type->ListInfo.item->size) { + fread(list.data, (size_t)type->ListInfo.item->size, (size_t)len, in); + } else { + for (int64_t i = 0; i < len; i++) + fread(list.data + i*list.stride, (size_t)type->ListInfo.item->size, 1, in); + } + *(List_t*)obj = list; +} + +// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0 diff --git a/src/stdlib/lists.h b/src/stdlib/lists.h new file mode 100644 index 00000000..a2853e48 --- /dev/null +++ b/src/stdlib/lists.h @@ -0,0 +1,137 @@ +#pragma once + +// Functions that operate on lists + +#include + +#include "datatypes.h" +#include "integers.h" +#include "types.h" +#include "util.h" + +// Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1 +#define List_get(item_type, arr_expr, index_expr, start, end) *({ \ + const List_t list = arr_expr; int64_t index = index_expr; \ + int64_t off = index + (index < 0) * (list.length + 1) - 1; \ + if (unlikely(off < 0 || off >= list.length)) \ + fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ", (int64_t)list.length, ")\n"); \ + (item_type*)(list.data + list.stride * off);}) +#define List_get_unchecked(type, x, i) *({ const List_t list = x; int64_t index = i; \ + int64_t off = index + (index < 0) * (list.length + 1) - 1; \ + (type*)(list.data + list.stride * off);}) +#define List_lvalue(item_type, arr_expr, index_expr, start, end) *({ \ + List_t *list = arr_expr; int64_t index = index_expr; \ + int64_t off = index + (index < 0) * (list->length + 1) - 1; \ + if (unlikely(off < 0 || off >= list->length)) \ + fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ", (int64_t)list->length, ")\n"); \ + if (list->data_refcount > 0) \ + List$compact(list, sizeof(item_type)); \ + (item_type*)(list->data + list->stride * off); }) +#define List_lvalue_unchecked(item_type, arr_expr, index_expr) *({ \ + List_t *list = arr_expr; int64_t index = index_expr; \ + int64_t off = index + (index < 0) * (list->length + 1) - 1; \ + if (list->data_refcount > 0) \ + List$compact(list, sizeof(item_type)); \ + (item_type*)(list->data + list->stride * off); }) +#define List_set(item_type, list, index, value, start, end) \ + List_lvalue(item_type, arr_expr, index, start, end) = value +#define is_atomic(x) _Generic(x, bool: true, int8_t: true, int16_t: true, int32_t: true, int64_t: true, float: true, double: true, default: false) +#define TypedList(t, ...) ({ t items[] = {__VA_ARGS__}; \ + (List_t){.length=sizeof(items)/sizeof(items[0]), \ + .stride=(int64_t)&items[1] - (int64_t)&items[0], \ + .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \ + .atomic=0, \ + .data_refcount=0}; }) +#define TypedListN(t, N, ...) ({ t items[N] = {__VA_ARGS__}; \ + (List_t){.length=N, \ + .stride=(int64_t)&items[1] - (int64_t)&items[0], \ + .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \ + .atomic=0, \ + .data_refcount=0}; }) +#define List(x, ...) ({ __typeof(x) items[] = {x, __VA_ARGS__}; \ + (List_t){.length=sizeof(items)/sizeof(items[0]), \ + .stride=(int64_t)&items[1] - (int64_t)&items[0], \ + .data=memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items, sizeof(items)), \ + .atomic=is_atomic(x), \ + .data_refcount=0}; }) +// List refcounts use a saturating add, where once it's at the max value, it stays there. +#define LIST_INCREF(list) (list).data_refcount += ((list).data_refcount < LIST_MAX_DATA_REFCOUNT) +#define LIST_DECREF(list) (list).data_refcount -= ((list).data_refcount < LIST_MAX_DATA_REFCOUNT) +#define LIST_COPY(list) ({ LIST_INCREF(list); list; }) + +#define List$insert_value(list, item_expr, index, padded_item_size) List$insert(list, (__typeof(item_expr)[1]){item_expr}, index, padded_item_size) +void List$insert(List_t *list, const void *item, Int_t index, int64_t padded_item_size); +void List$insert_all(List_t *list, List_t to_insert, Int_t index, int64_t padded_item_size); +void List$remove_at(List_t *list, Int_t index, Int_t count, int64_t padded_item_size); +void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type); +#define List$remove_item_value(list, item_expr, max, type) List$remove_item(list, (__typeof(item_expr)[1]){item_expr}, max, type) + +#define List$pop(arr_expr, index_expr, item_type, nonnone_var, nonnone_expr, none_expr) ({ \ + List_t *list = arr_expr; \ + Int_t index = index_expr; \ + int64_t index64 = Int64$from_int(index, false); \ + int64_t off = index64 + (index64 < 0) * (list->length + 1) - 1; \ + (off >= 0 && off < list->length) ? ({ \ + item_type nonnone_var = *(item_type*)(list->data + off*list->stride); \ + List$remove_at(list, index, I_small(1), sizeof(item_type)); \ + nonnone_expr; \ + }) : none_expr; }) + +OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type); +#define List$find_value(list, item_expr, type) ({ __typeof(item_expr) item = item_expr; List$find(list, &item, type); }) +OptionalInt_t List$first(List_t list, Closure_t predicate); +void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size); +List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size); +void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size); +List_t List$shuffled(List_t list, OptionalClosure_t random_int64, int64_t padded_item_size); +void *List$random(List_t list, OptionalClosure_t random_int64); +#define List$random_value(list, random_int64, t) ({ List_t _arr = list; if (_arr.length == 0) fail("Cannot get a random value from an empty list!"); *(t*)List$random(_arr, random_int64); }) +List_t List$sample(List_t list, Int_t n, List_t weights, Closure_t random_num, int64_t padded_item_size); +Table_t List$counts(List_t list, const TypeInfo_t *type); +void List$clear(List_t *list); +void List$compact(List_t *list, int64_t padded_item_size); +PUREFUNC bool List$has(List_t list, void *item, const TypeInfo_t *type); +#define List$has_value(list, item_expr, type) ({ __typeof(item_expr) item = item_expr; List$has(list, &item, type); }) +PUREFUNC List_t List$from(List_t list, Int_t first); +PUREFUNC List_t List$to(List_t list, Int_t last); +PUREFUNC List_t List$by(List_t list, Int_t stride, int64_t padded_item_size); +PUREFUNC List_t List$slice(List_t list, Int_t int_first, Int_t int_last); +PUREFUNC List_t List$reversed(List_t list, int64_t padded_item_size); +List_t List$concat(List_t x, List_t y, int64_t padded_item_size); +PUREFUNC uint64_t List$hash(const void *list, const TypeInfo_t *type); +PUREFUNC int32_t List$compare(const void *x, const void *y, const TypeInfo_t *type); +PUREFUNC bool List$equal(const void *x, const void *y, const TypeInfo_t *type); +PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t*); +Text_t List$as_text(const void *list, bool colorize, const TypeInfo_t *type); +void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size); +void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size); +#define List$heap_push_value(heap, _value, comparison, padded_item_size) ({ __typeof(_value) value = _value; List$heap_push(heap, &value, comparison, padded_item_size); }) +void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size); +#define List$heap_pop_value(heap, comparison, type, nonnone_var, nonnone_expr, none_expr) \ + ({ List_t *_heap = heap; \ + (_heap->length > 0) ? ({ \ + type nonnone_var = *(type*)_heap->data; \ + List$heap_pop(_heap, comparison, sizeof(type)); \ + nonnone_expr; \ + }) : none_expr; }) +Int_t List$binary_search(List_t list, void *target, Closure_t comparison); +#define List$binary_search_value(list, target, comparison) \ + ({ __typeof(target) _target = target; List$binary_search(list, &_target, comparison); }) +void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); +void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type); + +#define List$metamethods { \ + .as_text=List$as_text, \ + .compare=List$compare, \ + .equal=List$equal, \ + .hash=List$hash, \ + .is_none=List$is_none, \ + .serialize=List$serialize, \ + .deserialize=List$deserialize, \ +} + +#define List$info(item_info) &((TypeInfo_t){.size=sizeof(List_t), .align=__alignof__(List_t), \ + .tag=ListInfo, .ListInfo.item=item_info, \ + .metamethods=List$metamethods}) + +// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0 diff --git a/src/stdlib/metamethods.c b/src/stdlib/metamethods.c index a7622e0b..6ee52222 100644 --- a/src/stdlib/metamethods.c +++ b/src/stdlib/metamethods.c @@ -3,7 +3,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "bools.h" #include "bytes.h" #include "functiontype.h" @@ -61,7 +61,7 @@ public void _serialize(const void *obj, FILE *out, Table_t *pointers, const Type fwrite(obj, (size_t)type->size, 1, out); } -public Array_t generic_serialize(const void *x, const TypeInfo_t *type) +public List_t generic_serialize(const void *x, const TypeInfo_t *type) { char *buf = NULL; size_t size = 0; @@ -69,7 +69,7 @@ public Array_t generic_serialize(const void *x, const TypeInfo_t *type) Table_t pointers = {}; _serialize(x, stream, &pointers, type); fclose(stream); - Array_t bytes = { + List_t bytes = { .data=GC_MALLOC_ATOMIC(size), .length=(int64_t)size, .stride=1, @@ -80,7 +80,7 @@ public Array_t generic_serialize(const void *x, const TypeInfo_t *type) return bytes; } -public void _deserialize(FILE *input, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void _deserialize(FILE *input, void *outval, List_t *pointers, const TypeInfo_t *type) { if (type->metamethods.deserialize) { type->metamethods.deserialize(input, outval, pointers, type); @@ -90,13 +90,13 @@ public void _deserialize(FILE *input, void *outval, Array_t *pointers, const Typ fread(outval, (size_t)type->size, 1, input); } -public void generic_deserialize(Array_t bytes, void *outval, const TypeInfo_t *type) +public void generic_deserialize(List_t bytes, void *outval, const TypeInfo_t *type) { if (bytes.stride != 1) - Array$compact(&bytes, 1); + List$compact(&bytes, 1); FILE *input = fmemopen(bytes.data, (size_t)bytes.length, "r"); - Array_t pointers = {}; + List_t pointers = {}; _deserialize(input, outval, &pointers, type); fclose(input); } @@ -115,7 +115,7 @@ public void cannot_serialize(const void*, FILE*, Table_t*, const TypeInfo_t *typ } __attribute__((noreturn)) -public void cannot_deserialize(FILE*, void*, Array_t*, const TypeInfo_t *type) +public void cannot_deserialize(FILE*, void*, List_t*, const TypeInfo_t *type) { Text_t typestr = generic_as_text(NULL, false, type); fail("Values of type ", typestr, " cannot be serialized or deserialized!"); diff --git a/src/stdlib/metamethods.h b/src/stdlib/metamethods.h index a75fcf7f..ca0a1e7e 100644 --- a/src/stdlib/metamethods.h +++ b/src/stdlib/metamethods.h @@ -12,11 +12,11 @@ PUREFUNC int32_t generic_compare(const void *x, const void *y, const TypeInfo_t PUREFUNC bool generic_equal(const void *x, const void *y, const TypeInfo_t *type); Text_t generic_as_text(const void *obj, bool colorize, const TypeInfo_t *type); void _serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -Array_t generic_serialize(const void *x, const TypeInfo_t *type); -void _deserialize(FILE *input, void *outval, Array_t *pointers, const TypeInfo_t *type); -void generic_deserialize(Array_t bytes, void *outval, const TypeInfo_t *type); +List_t generic_serialize(const void *x, const TypeInfo_t *type); +void _deserialize(FILE *input, void *outval, List_t *pointers, const TypeInfo_t *type); +void generic_deserialize(List_t bytes, void *outval, const TypeInfo_t *type); int generic_print(const void *obj, bool colorize, const TypeInfo_t *type); void cannot_serialize(const void*, FILE*, Table_t*, const TypeInfo_t *type); -void cannot_deserialize(FILE*, void*, Array_t*, const TypeInfo_t *type); +void cannot_deserialize(FILE*, void*, List_t*, const TypeInfo_t *type); // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0 diff --git a/src/stdlib/nums.c b/src/stdlib/nums.c index ca8dcc4e..9edb8751 100644 --- a/src/stdlib/nums.c +++ b/src/stdlib/nums.c @@ -7,7 +7,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "nums.h" #include "string.h" #include "text.h" diff --git a/src/stdlib/optionals.c b/src/stdlib/optionals.c index d3309029..f33b471d 100644 --- a/src/stdlib/optionals.c +++ b/src/stdlib/optionals.c @@ -61,7 +61,7 @@ public void Optional$serialize(const void *obj, FILE *out, Table_t *pointers, co _serialize(obj, out, pointers, type->OptionalInfo.type); } -public void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void Optional$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type) { bool has_value = (bool)fgetc(in); const TypeInfo_t *nonnull = type->OptionalInfo.type; @@ -71,8 +71,8 @@ public void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, cons } else { if (nonnull->tag == TextInfo) *(Text_t*)outval = NONE_TEXT; - else if (nonnull->tag == ArrayInfo) - *(Array_t*)outval = (Array_t){.length=-1}; + else if (nonnull->tag == ListInfo) + *(List_t*)outval = (List_t){.length=-1}; else if (nonnull->tag == TableInfo) *(Table_t*)outval = (Table_t){.entries={.length=-1}}; else if (nonnull == &Num$info) diff --git a/src/stdlib/optionals.h b/src/stdlib/optionals.h index 8d25c5f1..2ffd5a50 100644 --- a/src/stdlib/optionals.h +++ b/src/stdlib/optionals.h @@ -10,7 +10,7 @@ #include "types.h" #include "util.h" -#define NONE_ARRAY ((Array_t){.length=-1}) +#define NONE_LIST ((List_t){.length=-1}) #define NONE_BOOL ((OptionalBool_t)2) #define NONE_INT ((OptionalInt_t){.small=0}) #define NONE_TABLE ((OptionalTable_t){.entries.length=-1}) @@ -24,7 +24,7 @@ PUREFUNC int32_t Optional$compare(const void *x, const void *y, const TypeInfo_t PUREFUNC bool Optional$equal(const void *x, const void *y, const TypeInfo_t *type); Text_t Optional$as_text(const void *obj, bool colorize, const TypeInfo_t *type); void Optional$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type); +void Optional$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type); #define Optional$metamethods { \ .hash=Optional$hash, \ diff --git a/src/stdlib/paths.c b/src/stdlib/paths.c index 7a5346f5..cad0e0ff 100644 --- a/src/stdlib/paths.c +++ b/src/stdlib/paths.c @@ -17,7 +17,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "enums.h" #include "files.h" #include "integers.h" @@ -37,16 +37,16 @@ static const Path_t HOME_PATH = {.type.$tag=PATH_HOME}, ROOT_PATH = {.type.$tag=PATH_ABSOLUTE}, CURDIR_PATH = {.type.$tag=PATH_RELATIVE}; -static void clean_components(Array_t *components) +static void clean_components(List_t *components) { for (int64_t i = 0; i < components->length; ) { Text_t *component = (Text_t*)(components->data + i*components->stride); if (component->length == 0 || Text$equal_values(*component, Text("."))) { - Array$remove_at(components, I(i+1), I(1), sizeof(Text_t)); + List$remove_at(components, I(i+1), I(1), sizeof(Text_t)); } else if (i > 0 && Text$equal_values(*component, Text(".."))) { Text_t *prev = (Text_t*)(components->data + (i-1)*components->stride); if (!Text$equal_values(*prev, Text(".."))) { - Array$remove_at(components, I(i), I(2), sizeof(Text_t)); + List$remove_at(components, I(i), I(2), sizeof(Text_t)); i -= 1; } else { i += 1; @@ -86,10 +86,10 @@ public Path_t Path$from_str(const char *str) && result.components.length > 1 && !Text$equal_values(Text(".."), *(Text_t*)(result.components.data + result.components.stride*(result.components.length-1)))) { // Pop off /foo/baz/.. -> /foo - Array$remove_at(&result.components, I(result.components.length), I(1), sizeof(Text_t)); + List$remove_at(&result.components, I(result.components.length), I(1), sizeof(Text_t)); } else { Text_t component = Text$from_strn(str, component_len); - Array$insert_value(&result.components, component, I(0), sizeof(Text_t)); + List$insert_value(&result.components, component, I(0), sizeof(Text_t)); } str += component_len; } @@ -107,7 +107,7 @@ public Path_t Path$expand_home(Path_t path) { if (path.type.$tag == PATH_HOME) { Path_t pwd = Path$from_str(getenv("HOME")); - Array_t components = Array$concat(pwd.components, path.components, sizeof(Text_t)); + List_t components = List$concat(pwd.components, path.components, sizeof(Text_t)); assert(components.length == path.components.length + pwd.components.length); clean_components(&components); path = (Path_t){.type.$tag=PATH_ABSOLUTE, .components=components}; @@ -119,11 +119,11 @@ public Path_t Path$_concat(int n, Path_t items[n]) { assert(n > 0); Path_t result = items[0]; - ARRAY_INCREF(result.components); + LIST_INCREF(result.components); for (int i = 1; i < n; i++) { if (items[i].type.$tag != PATH_RELATIVE) fail("Cannot concatenate an absolute or home-based path onto another path: (", items[i], ")"); - Array$insert_all(&result.components, items[i].components, I(0), sizeof(Text_t)); + List$insert_all(&result.components, items[i].components, I(0), sizeof(Text_t)); } clean_components(&result.components); return result; @@ -134,8 +134,8 @@ public Path_t Path$resolved(Path_t path, Path_t relative_to) if (path.type.$tag == PATH_RELATIVE && !(relative_to.type.$tag == PATH_RELATIVE && relative_to.components.length == 0)) { Path_t result = {.type.$tag=relative_to.type.$tag}; result.components = relative_to.components; - ARRAY_INCREF(result.components); - Array$insert_all(&result.components, path.components, I(0), sizeof(Text_t)); + LIST_INCREF(result.components); + List$insert_all(&result.components, path.components, I(0), sizeof(Text_t)); clean_components(&result.components); return result; } @@ -157,11 +157,11 @@ public Path_t Path$relative_to(Path_t path, Path_t relative_to) } for (int64_t i = shared; i < relative_to.components.length; i++) - Array$insert_value(&result.components, Text(".."), I(1), sizeof(Text_t)); + List$insert_value(&result.components, Text(".."), I(1), sizeof(Text_t)); for (int64_t i = shared; i < path.components.length; i++) { Text_t *p = (Text_t*)(path.components.data + i*path.components.stride); - Array$insert(&result.components, p, I(0), sizeof(Text_t)); + List$insert(&result.components, p, I(0), sizeof(Text_t)); } //clean_components(&result.components); return result; @@ -278,7 +278,7 @@ public OptionalInt64_t Path$changed(Path_t path, bool follow_symlinks) return (OptionalInt64_t){.value=(int64_t)sb.st_ctime}; } -static void _write(Path_t path, Array_t bytes, int mode, int permissions) +static void _write(Path_t path, List_t bytes, int mode, int permissions) { path = Path$expand_home(path); const char *path_str = Path$as_c_string(path); @@ -287,7 +287,7 @@ static void _write(Path_t path, Array_t bytes, int mode, int permissions) fail("Could not write to file: ", path_str, "\n", strerror(errno)); if (bytes.stride != 1) - Array$compact(&bytes, 1); + List$compact(&bytes, 1); ssize_t written = write(fd, bytes.data, (size_t)bytes.length); if (written != (ssize_t)bytes.length) fail("Could not write to file: ", path_str, "\n", strerror(errno)); @@ -296,36 +296,36 @@ static void _write(Path_t path, Array_t bytes, int mode, int permissions) public void Path$write(Path_t path, Text_t text, int permissions) { - Array_t bytes = Text$utf8_bytes(text); + List_t bytes = Text$utf8_bytes(text); _write(path, bytes, O_WRONLY | O_CREAT | O_TRUNC, permissions); } -public void Path$write_bytes(Path_t path, Array_t bytes, int permissions) +public void Path$write_bytes(Path_t path, List_t bytes, int permissions) { _write(path, bytes, O_WRONLY | O_CREAT | O_TRUNC, permissions); } public void Path$append(Path_t path, Text_t text, int permissions) { - Array_t bytes = Text$utf8_bytes(text); + List_t bytes = Text$utf8_bytes(text); _write(path, bytes, O_WRONLY | O_APPEND | O_CREAT, permissions); } -public void Path$append_bytes(Path_t path, Array_t bytes, int permissions) +public void Path$append_bytes(Path_t path, List_t bytes, int permissions) { _write(path, bytes, O_WRONLY | O_APPEND | O_CREAT, permissions); } -public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count) +public OptionalList_t Path$read_bytes(Path_t path, OptionalInt_t count) { path = Path$expand_home(path); int fd = open(Path$as_c_string(path), O_RDONLY); if (fd == -1) - return NONE_ARRAY; + return NONE_LIST; struct stat sb; if (fstat(fd, &sb) != 0) - return NONE_ARRAY; + return NONE_LIST; int64_t const target_count = count.small ? Int64$from_int(count, false) : INT64_MAX; if (target_count < 0) @@ -340,7 +340,7 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count) if (count.small && (int64_t)sb.st_size < target_count) fail("Could not read ", target_count, " bytes from ", path, " (only got ", (uint64_t)sb.st_size, ")"); int64_t len = count.small ? target_count : (int64_t)sb.st_size; - return (Array_t){.data=content, .atomic=1, .stride=1, .length=len}; + return (List_t){.data=content, .atomic=1, .stride=1, .length=len}; } else { size_t capacity = 256, len = 0; char *content = GC_MALLOC_ATOMIC(capacity); @@ -351,7 +351,7 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count) ssize_t just_read = read(fd, chunk, to_read); if (just_read < 0) { close(fd); - return NONE_ARRAY; + return NONE_LIST; } else if (just_read == 0) { if (errno == EAGAIN || errno == EINTR) continue; @@ -369,13 +369,13 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count) close(fd); if (count.small != 0 && (int64_t)len < target_count) fail("Could not read ", target_count, " bytes from ", path, " (only got ", (uint64_t)len, ")"); - return (Array_t){.data=content, .atomic=1, .stride=1, .length=len}; + return (List_t){.data=content, .atomic=1, .stride=1, .length=len}; } } public OptionalText_t Path$read(Path_t path) { - Array_t bytes = Path$read_bytes(path, NONE_INT); + List_t bytes = Path$read_bytes(path, NONE_INT); if (bytes.length < 0) return NONE_TEXT; return Text$from_bytes(bytes); } @@ -471,11 +471,11 @@ public void Path$create_directory(Path_t path, int permissions) fail("Could not create directory: ", c_path, " (", strerror(errno), ")"); } -static Array_t _filtered_children(Path_t path, bool include_hidden, mode_t filter) +static List_t _filtered_children(Path_t path, bool include_hidden, mode_t filter) { path = Path$expand_home(path); struct dirent *dir; - Array_t children = {}; + List_t children = {}; const char *path_str = Path$as_c_string(path); size_t path_len = strlen(path_str); DIR *d = opendir(path_str); @@ -499,23 +499,23 @@ static Array_t _filtered_children(Path_t path, bool include_hidden, mode_t filte continue; Path_t child = Path$from_str(child_str); - Array$insert(&children, &child, I(0), sizeof(Path_t)); + List$insert(&children, &child, I(0), sizeof(Path_t)); } closedir(d); return children; } -public Array_t Path$children(Path_t path, bool include_hidden) +public List_t Path$children(Path_t path, bool include_hidden) { return _filtered_children(path, include_hidden, (mode_t)-1); } -public Array_t Path$files(Path_t path, bool include_hidden) +public List_t Path$files(Path_t path, bool include_hidden) { return _filtered_children(path, include_hidden, S_IFREG); } -public Array_t Path$subdirectories(Path_t path, bool include_hidden) +public List_t Path$subdirectories(Path_t path, bool include_hidden) { return _filtered_children(path, include_hidden, S_IFDIR); } @@ -535,7 +535,7 @@ public Path_t Path$unique_directory(Path_t path) return Path$from_str(created); } -public Path_t Path$write_unique_bytes(Path_t path, Array_t bytes) +public Path_t Path$write_unique_bytes(Path_t path, List_t bytes) { path = Path$expand_home(path); const char *path_str = Path$as_c_string(path); @@ -555,7 +555,7 @@ public Path_t Path$write_unique_bytes(Path_t path, Array_t bytes) fail("Could not write to unique file: ", buf, "\n", strerror(errno)); if (bytes.stride != 1) - Array$compact(&bytes, 1); + List$compact(&bytes, 1); ssize_t written = write(fd, bytes.data, (size_t)bytes.length); if (written != (ssize_t)bytes.length) @@ -575,11 +575,11 @@ public Path_t Path$parent(Path_t path) return path; } else if (path.components.length > 0 && !Text$equal_values(*(Text_t*)(path.components.data + path.components.stride*(path.components.length-1)), Text(".."))) { - return (Path_t){.type.$tag=path.type.$tag, .components=Array$slice(path.components, I(1), I(-2))}; + return (Path_t){.type.$tag=path.type.$tag, .components=List$slice(path.components, I(1), I(-2))}; } else { Path_t result = {.type.$tag=path.type.$tag, .components=path.components}; - ARRAY_INCREF(result.components); - Array$insert_value(&result.components, Text(".."), I(0), sizeof(Text_t)); + LIST_INCREF(result.components); + List$insert_value(&result.components, Text(".."), I(0), sizeof(Text_t)); return result; } } @@ -610,8 +610,8 @@ public Path_t Path$with_component(Path_t path, Text_t component) .type.$tag=path.type.$tag, .components=path.components, }; - ARRAY_INCREF(result.components); - Array$insert(&result.components, &component, I(0), sizeof(Text_t)); + LIST_INCREF(result.components); + List$insert(&result.components, &component, I(0), sizeof(Text_t)); clean_components(&result.components); return result; } @@ -625,9 +625,9 @@ public Path_t Path$with_extension(Path_t path, Text_t extension, bool replace) .type.$tag=path.type.$tag, .components=path.components, }; - ARRAY_INCREF(result.components); + LIST_INCREF(result.components); Text_t last = *(Text_t*)(path.components.data + path.components.stride*(path.components.length-1)); - Array$remove_at(&result.components, I(-1), I(1), sizeof(Text_t)); + List$remove_at(&result.components, I(-1), I(1), sizeof(Text_t)); if (replace) { const char *base = Text$as_c_string(last); const char *dot = strchr(base + 1, '.'); @@ -636,7 +636,7 @@ public Path_t Path$with_extension(Path_t path, Text_t extension, bool replace) } last = Text$concat(last, extension); - Array$insert(&result.components, &last, I(0), sizeof(Text_t)); + List$insert(&result.components, &last, I(0), sizeof(Text_t)); return result; } @@ -685,21 +685,21 @@ public OptionalClosure_t Path$by_line(Path_t path) return (Closure_t){.fn=(void*)_next_line, .userdata=wrapper}; } -public Array_t Path$glob(Path_t path) +public List_t Path$glob(Path_t path) { glob_t glob_result; int status = glob(Path$as_c_string(path), GLOB_BRACE | GLOB_TILDE, NULL, &glob_result); if (status != 0 && status != GLOB_NOMATCH) fail("Failed to perform globbing"); - Array_t glob_files = {}; + List_t glob_files = {}; for (size_t i = 0; i < glob_result.gl_pathc; i++) { size_t len = strlen(glob_result.gl_pathv[i]); if ((len >= 2 && glob_result.gl_pathv[i][len-1] == '.' && glob_result.gl_pathv[i][len-2] == '/') || (len >= 2 && glob_result.gl_pathv[i][len-1] == '.' && glob_result.gl_pathv[i][len-2] == '.' && glob_result.gl_pathv[i][len-3] == '/')) continue; Path_t p = Path$from_str(glob_result.gl_pathv[i]); - Array$insert(&glob_files, &p, I(0), sizeof(Path_t)); + List$insert(&glob_files, &p, I(0), sizeof(Path_t)); } return glob_files; } @@ -730,7 +730,7 @@ public PUREFUNC int32_t Path$compare(const void *va, const void *vb, const TypeI Path_t *a = (Path_t*)va, *b = (Path_t*)vb; int diff = ((int)a->type.$tag - (int)b->type.$tag); if (diff != 0) return diff; - return Array$compare(&a->components, &b->components, Array$info(&Text$info)); + return List$compare(&a->components, &b->components, List$info(&Text$info)); } public PUREFUNC bool Path$equal(const void *va, const void *vb, const TypeInfo_t *type) @@ -738,13 +738,13 @@ public PUREFUNC bool Path$equal(const void *va, const void *vb, const TypeInfo_t (void)type; Path_t *a = (Path_t*)va, *b = (Path_t*)vb; if (a->type.$tag != b->type.$tag) return false; - return Array$equal(&a->components, &b->components, Array$info(&Text$info)); + return List$equal(&a->components, &b->components, List$info(&Text$info)); } public PUREFUNC bool Path$equal_values(Path_t a, Path_t b) { if (a.type.$tag != b.type.$tag) return false; - return Array$equal(&a.components, &b.components, Array$info(&Text$info)); + return List$equal(&a.components, &b.components, List$info(&Text$info)); } public int Path$print(FILE *f, Path_t path) @@ -809,15 +809,15 @@ public void Path$serialize(const void *obj, FILE *out, Table_t *pointers, const (void)type; Path_t *path = (Path_t*)obj; fputc((int)path->type.$tag, out); - Array$serialize(&path->components, out, pointers, Array$info(&Text$info)); + List$serialize(&path->components, out, pointers, List$info(&Text$info)); } -public void Path$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type) +public void Path$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type) { (void)type; Path_t path = {}; path.type.$tag = fgetc(in); - Array$deserialize(in, &path.components, pointers, Array$info(&Text$info)); + List$deserialize(in, &path.components, pointers, List$info(&Text$info)); *(Path_t*)obj = path; } diff --git a/src/stdlib/paths.h b/src/stdlib/paths.h index 9be81bdf..31d676b7 100644 --- a/src/stdlib/paths.h +++ b/src/stdlib/paths.h @@ -32,22 +32,22 @@ OptionalInt64_t Path$modified(Path_t path, bool follow_symlinks); OptionalInt64_t Path$accessed(Path_t path, bool follow_symlinks); OptionalInt64_t Path$changed(Path_t path, bool follow_symlinks); void Path$write(Path_t path, Text_t text, int permissions); -void Path$write_bytes(Path_t path, Array_t bytes, int permissions); +void Path$write_bytes(Path_t path, List_t bytes, int permissions); void Path$append(Path_t path, Text_t text, int permissions); -void Path$append_bytes(Path_t path, Array_t bytes, int permissions); +void Path$append_bytes(Path_t path, List_t bytes, int permissions); OptionalText_t Path$read(Path_t path); -OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t limit); +OptionalList_t Path$read_bytes(Path_t path, OptionalInt_t limit); void Path$set_owner(Path_t path, OptionalText_t owner, OptionalText_t group, bool follow_symlinks); OptionalText_t Path$owner(Path_t path, bool follow_symlinks); OptionalText_t Path$group(Path_t path, bool follow_symlinks); void Path$remove(Path_t path, bool ignore_missing); void Path$create_directory(Path_t path, int permissions); -Array_t Path$children(Path_t path, bool include_hidden); -Array_t Path$files(Path_t path, bool include_hidden); -Array_t Path$subdirectories(Path_t path, bool include_hidden); +List_t Path$children(Path_t path, bool include_hidden); +List_t Path$files(Path_t path, bool include_hidden); +List_t Path$subdirectories(Path_t path, bool include_hidden); Path_t Path$unique_directory(Path_t path); Path_t Path$write_unique(Path_t path, Text_t text); -Path_t Path$write_unique_bytes(Path_t path, Array_t bytes); +Path_t Path$write_unique_bytes(Path_t path, List_t bytes); Path_t Path$parent(Path_t path); Text_t Path$base_name(Path_t path); Text_t Path$extension(Path_t path, bool full); @@ -55,7 +55,7 @@ Path_t Path$with_component(Path_t path, Text_t component); Path_t Path$with_extension(Path_t path, Text_t extension, bool replace); Path_t Path$current_dir(void); Closure_t Path$by_line(Path_t path); -Array_t Path$glob(Path_t path); +List_t Path$glob(Path_t path); uint64_t Path$hash(const void *obj, const TypeInfo_t*); int32_t Path$compare(const void *a, const void *b, const TypeInfo_t *type); @@ -64,7 +64,7 @@ bool Path$equal_values(Path_t a, Path_t b); Text_t Path$as_text(const void *obj, bool color, const TypeInfo_t *type); bool Path$is_none(const void *obj, const TypeInfo_t *type); void Path$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Path$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type); +void Path$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type); extern const TypeInfo_t Path$info; extern const TypeInfo_t PathType$info; diff --git a/src/stdlib/pointers.c b/src/stdlib/pointers.c index 76e882ec..b674ac6f 100644 --- a/src/stdlib/pointers.c +++ b/src/stdlib/pointers.c @@ -104,7 +104,7 @@ public void Pointer$serialize(const void *obj, FILE *out, Table_t *pointers, con _serialize(ptr, out, pointers, type->PointerInfo.pointed); } -public void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void Pointer$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type) { int64_t id = 0; Int64$deserialize(in, &id, pointers, &Int64$info); @@ -112,7 +112,7 @@ public void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const if (id > pointers->length) { void *obj = GC_MALLOC((size_t)type->PointerInfo.pointed->size); - Array$insert(pointers, &obj, I(0), sizeof(void*)); + List$insert(pointers, &obj, I(0), sizeof(void*)); _deserialize(in, obj, pointers, type->PointerInfo.pointed); *(void**)outval = obj; } else { diff --git a/src/stdlib/pointers.h b/src/stdlib/pointers.h index 165a5184..b818452e 100644 --- a/src/stdlib/pointers.h +++ b/src/stdlib/pointers.h @@ -14,7 +14,7 @@ PUREFUNC int32_t Pointer$compare(const void *x, const void *y, const TypeInfo_t PUREFUNC bool Pointer$equal(const void *x, const void *y, const TypeInfo_t *type); PUREFUNC bool Pointer$is_none(const void *x, const TypeInfo_t*); void Pointer$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type); +void Pointer$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type); #define Null(t) (t*)NULL #define POINTER_TYPE(_sigil, _pointed) (&(TypeInfo_t){\ diff --git a/src/stdlib/stdlib.c b/src/stdlib/stdlib.c index 8d3a8081..e8cfe06a 100644 --- a/src/stdlib/stdlib.c +++ b/src/stdlib/stdlib.c @@ -158,8 +158,8 @@ static bool parse_single_arg(const TypeInfo_t *info, char *arg, void *dest) Text_t t = generic_as_text(NULL, false, info); print_err("Unsupported multi-argument struct type for argument parsing: ", t); - } else if (info->tag == ArrayInfo) { - print_err("Array arguments must be specified as `--flag ...` not `--flag=...`"); + } else if (info->tag == ListInfo) { + print_err("List arguments must be specified as `--flag ...` not `--flag=...`"); } else if (info->tag == TableInfo) { print_err("Table arguments must be specified as `--flag ...` not `--flag=...`"); } else { @@ -168,13 +168,13 @@ static bool parse_single_arg(const TypeInfo_t *info, char *arg, void *dest) } } -static Array_t parse_array(const TypeInfo_t *item_info, int n, char *args[]) +static List_t parse_list(const TypeInfo_t *item_info, int n, char *args[]) { int64_t padded_size = item_info->size; if ((padded_size % item_info->align) > 0) padded_size = padded_size + item_info->align - (padded_size % item_info->align); - Array_t items = { + List_t items = { .stride=padded_size, .length=n, .data=GC_MALLOC((size_t)(padded_size*n)), @@ -199,7 +199,7 @@ static Table_t parse_table(const TypeInfo_t *table, int n, char *args[]) if ((padded_size % key->align) > 0) padded_size = padded_size + key->align - (padded_size % key->align); - Array_t entries = { + List_t entries = { .stride=padded_size, .length=n, .data=GC_MALLOC((size_t)(padded_size*n)), @@ -262,7 +262,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, char after_name = argv[i][2+strlen(spec[s].name)]; if (after_name == '\0') { // --foo val used_args[i] = true; - if (non_opt_type->tag == ArrayInfo) { + if (non_opt_type->tag == ListInfo) { int num_args = 0; while (i + 1 + num_args < argc) { if (argv[i+1+num_args][0] == '-') @@ -271,7 +271,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, num_args += 1; } populated_args[s] = true; - *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i+1]); + *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i+1]); } else if (non_opt_type->tag == TableInfo) { int num_args = 0; while (i + 1 + num_args < argc) { @@ -322,7 +322,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, while (non_opt_type->tag == OptionalInfo) non_opt_type = non_opt_type->OptionalInfo.type; - if (non_opt_type->tag == ArrayInfo) { + if (non_opt_type->tag == ListInfo) { if (f[1]) print_err("No value provided for ", flag, "\n", usage); int num_args = 0; while (i + 1 + num_args < argc) { @@ -332,7 +332,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, num_args += 1; } populated_args[s] = true; - *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i+1]); + *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i+1]); } else if (non_opt_type->tag == TableInfo) { int num_args = 0; while (i + 1 + num_args < argc) { @@ -398,7 +398,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, if (non_opt_type == &Bool$info) goto next_non_bool_flag; - if (non_opt_type->tag == ArrayInfo) { + if (non_opt_type->tag == ListInfo) { int num_args = 0; while (i + num_args < argc) { if (!ignore_dashes && argv[i+num_args][0] == '-') @@ -407,7 +407,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, num_args += 1; } populated_args[s] = true; - *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i]); + *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i]); } else if (non_opt_type->tag == TableInfo) { int num_args = 0; while (i + num_args < argc) { @@ -428,8 +428,8 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help, for (int s = 0; s < spec_len; s++) { if (!populated_args[s] && spec[s].required) { - if (spec[s].type->tag == ArrayInfo) - *(OptionalArray_t*)spec[s].dest = (Array_t){}; + if (spec[s].type->tag == ListInfo) + *(OptionalList_t*)spec[s].dest = (List_t){}; else if (spec[s].type->tag == TableInfo) *(OptionalTable_t*)spec[s].dest = (Table_t){}; else diff --git a/src/stdlib/structs.c b/src/stdlib/structs.c index 53b0e0a4..9a14779e 100644 --- a/src/stdlib/structs.c +++ b/src/stdlib/structs.c @@ -3,7 +3,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "bools.h" #include "functiontype.h" #include "metamethods.h" @@ -211,7 +211,7 @@ public void Struct$serialize(const void *obj, FILE *out, Table_t *pointers, cons } } -public void Struct$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void Struct$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type) { ptrdiff_t byte_offset = 0; ptrdiff_t bit_offset = 0; diff --git a/src/stdlib/structs.h b/src/stdlib/structs.h index bab702cd..c9c6c40a 100644 --- a/src/stdlib/structs.h +++ b/src/stdlib/structs.h @@ -15,7 +15,7 @@ PUREFUNC bool PackedData$equal(const void *x, const void *y, const TypeInfo_t *t PUREFUNC Text_t Struct$as_text(const void *obj, bool colorize, const TypeInfo_t *type); PUREFUNC bool Struct$is_none(const void *obj, const TypeInfo_t *type); void Struct$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Struct$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type); +void Struct$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type); #define Struct$metamethods { \ .hash=Struct$hash, \ diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c index d59bc113..3cb2e742 100644 --- a/src/stdlib/tables.c +++ b/src/stdlib/tables.c @@ -16,7 +16,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "c_strings.h" #include "datatypes.h" #include "memory.h" @@ -97,7 +97,7 @@ static INLINE void hshow(const Table_t *t) static void maybe_copy_on_write(Table_t *t, const TypeInfo_t *type) { if (t->entries.data_refcount != 0) - Array$compact(&t->entries, (int64_t)entry_size(type)); + List$compact(&t->entries, (int64_t)entry_size(type)); if (t->bucket_info && t->bucket_info->data_refcount != 0) { size_t size = sizeof(bucket_info_t) + sizeof(bucket_t[t->bucket_info->count]); @@ -273,7 +273,7 @@ public void *Table$reserve(Table_t *t, const void *key, const void *value, const memcpy(buf + value_offset(type), value, (size_t)value_size); else memset(buf + value_offset(type), 0, (size_t)value_size); - Array$insert(&t->entries, buf, I(0), (int64_t)entry_size(type)); + List$insert(&t->entries, buf, I(0), (int64_t)entry_size(type)); int64_t entry_index = t->entries.length-1; void *entry = GET_ENTRY(*t, entry_index); @@ -343,7 +343,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type) // instead of O(N) int64_t last_entry = t->entries.length-1; if (bucket->index != last_entry) { - hdebug("Removing key/value from the middle of the entries array\n"); + hdebug("Removing key/value from the middle of the entries list\n"); // Find the bucket that points to the last entry's index: uint64_t i = HASH_KEY(*t, GET_ENTRY(*t, last_entry)); @@ -353,7 +353,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type) // where the removed entry currently sits): t->bucket_info->buckets[i].index = bucket->index; - // Clobber the entry being removed (in the middle of the array) with + // Clobber the entry being removed (in the middle of the list) with // the last entry: memcpy(GET_ENTRY(*t, bucket->index), GET_ENTRY(*t, last_entry), entry_size(type)); } @@ -361,7 +361,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type) // Last entry is being removed, so clear it out to be safe: memset(GET_ENTRY(*t, last_entry), 0, entry_size(type)); - Array$remove_at(&t->entries, I(t->entries.length), I(1), (int64_t)entry_size(type)); + List$remove_at(&t->entries, I(t->entries.length), I(1), (int64_t)entry_size(type)); int64_t bucket_to_clear; if (prev) { // Middle (or end) of a chain @@ -399,7 +399,7 @@ public void Table$clear(Table_t *t) public Table_t Table$sorted(Table_t t, const TypeInfo_t *type) { Closure_t cmp = (Closure_t){.fn=generic_compare, .userdata=(void*)type->TableInfo.key}; - Array_t entries = Array$sorted(t.entries, cmp, (int64_t)entry_size(type)); + List_t entries = List$sorted(t.entries, cmp, (int64_t)entry_size(type)); return Table$from_entries(entries, type); } @@ -445,10 +445,10 @@ PUREFUNC public int32_t Table$compare(const void *vx, const void *vy, const Type // Table comparison rules: // - If two tables have different keys, then compare as if comparing a - // sorted array of the keys of the two tables: + // sorted list of the keys of the two tables: // `x.keys.sorted() <> y.keys.sorted()` - // - Otherwise, compare as if comparing arrays of values for the sorted key - // arrays: + // - Otherwise, compare as if comparing lists of values for the sorted key + // lists: // `[x[k] for k in x.keys.sorted()] <> [y[k] for k in y.keys.sorted()]` // // We can do this in _linear_ time if we find the smallest `k` such that @@ -612,7 +612,7 @@ public Text_t Table$as_text(const void *obj, bool colorize, const TypeInfo_t *ty return text; } -public Table_t Table$from_entries(Array_t entries, const TypeInfo_t *type) +public Table_t Table$from_entries(List_t entries, const TypeInfo_t *type) { assert(type->tag == TableInfo); if (entries.length == 0) @@ -776,7 +776,7 @@ public void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wstack-protector" #endif -public void Table$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type) +public void Table$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type) { int64_t len; Int64$deserialize(in, &len, pointers, &Int$info); diff --git a/src/stdlib/tables.h b/src/stdlib/tables.h index 979da5e7..35673eaf 100644 --- a/src/stdlib/tables.h +++ b/src/stdlib/tables.h @@ -6,14 +6,14 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "datatypes.h" #include "types.h" #include "util.h" #define Table(key_t, val_t, key_info, value_info, fb, N, ...) ({ \ struct { key_t k; val_t v; } ents[N] = {__VA_ARGS__}; \ - Table_t table = Table$from_entries((Array_t){ \ + Table_t table = Table$from_entries((List_t){ \ .data=memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \ .length=sizeof(ents)/sizeof(ents[0]), \ .stride=(void*)&ents[1] - (void*)&ents[0], \ @@ -22,14 +22,14 @@ table; }) #define Set(item_t, item_info, N, ...) ({ \ item_t ents[N] = {__VA_ARGS__}; \ - Table_t set = Table$from_entries((Array_t){ \ + Table_t set = Table$from_entries((List_t){ \ .data=memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \ .length=sizeof(ents)/sizeof(ents[0]), \ .stride=(void*)&ents[1] - (void*)&ents[0], \ }, Set$info(item_info)); \ set; }) -Table_t Table$from_entries(Array_t entries, const TypeInfo_t *type); +Table_t Table$from_entries(List_t entries, const TypeInfo_t *type); void *Table$get(Table_t t, const void *key, const TypeInfo_t *type); #define Table$get_optional(table_expr, key_t, val_t, key_expr, nonnull_var, nonnull_expr, null_expr, info_expr) ({ \ const Table_t t = table_expr; const key_t k = key_expr; \ @@ -71,7 +71,7 @@ PUREFUNC bool Table$is_superset_of(Table_t a, Table_t b, bool strict, const Type void Table$clear(Table_t *t); Table_t Table$sorted(Table_t t, const TypeInfo_t *type); void Table$mark_copy_on_write(Table_t *t); -#define TABLE_INCREF(t) ({ ARRAY_INCREF((t).entries); if ((t).bucket_info) (t).bucket_info->data_refcount += ((t).bucket_info->data_refcount < TABLE_MAX_DATA_REFCOUNT); }) +#define TABLE_INCREF(t) ({ LIST_INCREF((t).entries); if ((t).bucket_info) (t).bucket_info->data_refcount += ((t).bucket_info->data_refcount < TABLE_MAX_DATA_REFCOUNT); }) #define TABLE_COPY(t) ({ TABLE_INCREF(t); t; }) PUREFUNC int32_t Table$compare(const void *x, const void *y, const TypeInfo_t *type); PUREFUNC bool Table$equal(const void *x, const void *y, const TypeInfo_t *type); @@ -86,7 +86,7 @@ void Table$str_set(Table_t *t, const char *key, const void *value); void *Table$str_reserve(Table_t *t, const char *key, const void *value); void Table$str_remove(Table_t *t, const char *key); void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type); -void Table$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type); +void Table$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type); #define Table$length(t) ((t).entries.length) diff --git a/src/stdlib/text.c b/src/stdlib/text.c index b3e9cebb..3346bf4b 100644 --- a/src/stdlib/text.c +++ b/src/stdlib/text.c @@ -27,7 +27,7 @@ // is basically what Zalgo text is). // // There are a lot of benefits to storing unicode text with one grapheme -// cluster per index in a densely packed array instead of storing the text as +// cluster per index in a densely packed list instead of storing the text as // variable-width UTF8-encoded bytes. It lets us have one canonical length for // the text that can be precomputed and is meaningful to users. It lets us // quickly get the Nth "letter" in the text. Substring slicing is fast. @@ -38,7 +38,7 @@ // Graphemes, aka NFG). A synthetic grapheme is a negative 32-bit signed // integer that represents a multi-codepoint grapheme cluster that has been // encountered during the program's runtime. These clusters are stored in a -// lookup array and hash map so that we can rapidly convert between the +// lookup list and hash map so that we can rapidly convert between the // synthetic grapheme integer ID and the unicode codepoints associated with it. // Essentially, it's like we create a supplement to the unicode standard with // things that would be nice if they had their own codepoint so things worked @@ -49,7 +49,7 @@ // WITH ACUTE This would be stored as: (int32_t[]){0x48, 0xE9} Example 2: // U+0048, U+0065, U+0309 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E, // COMBINING VERTICAL LINE BELOW This would be stored as: (int32_t[]){0x48, -2} -// Where -2 is used as a lookup in an array that holds the actual unicode +// Where -2 is used as a lookup in a list that holds the actual unicode // codepoints: (ucs4_t[]){0x65, 0x0309} #include @@ -68,7 +68,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "integers.h" #include "tables.h" #include "text.h" @@ -86,7 +86,7 @@ typedef struct { // Synthetic grapheme clusters (clusters of more than one codepoint): static Table_t grapheme_ids_by_codepoints = {}; // ucs4_t* length-prefixed codepoints -> int32_t ID -// This will hold a dynamically growing array of synthetic graphemes: +// This will hold a dynamically growing list of synthetic graphemes: static synthetic_grapheme_t *synthetic_graphemes = NULL; static int32_t synthetic_grapheme_capacity = 0; static int32_t num_synthetic_graphemes = 0; @@ -733,7 +733,7 @@ Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize) // Intentionally overallocate here: allocate assuming each codepoint is a // grapheme cluster. If that's not true, we'll have extra space at the end - // of the array, but the length will still be calculated correctly. + // of the list, but the length will still be calculated correctly. int32_t *graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[num_codepoints])); struct Text_s ret = { .tag=TEXT_GRAPHEMES, @@ -1067,10 +1067,10 @@ public Text_t Text$translate(Text_t text, Table_t translations) TextIter_t text_state = NEW_TEXT_ITER_STATE(text); Text_t result = EMPTY_TEXT; int64_t span_start = 0; - Array_t replacement_array = translations.entries; + List_t replacement_list = translations.entries; for (int64_t i = 0; i < text.length; ) { - for (int64_t r = 0; r < replacement_array.length; r++) { - struct { Text_t target, replacement; } *entry = replacement_array.data + r*replacement_array.stride; + for (int64_t r = 0; r < replacement_list.length; r++) { + struct { Text_t target, replacement; } *entry = replacement_list.data + r*replacement_list.stride; TextIter_t target_state = NEW_TEXT_ITER_STATE(entry->target); if (_matches(&text_state, &target_state, i)) { if (i > span_start) @@ -1122,36 +1122,36 @@ public bool Text$has(Text_t text, Text_t target) return false; } -public Array_t Text$split(Text_t text, Text_t delimiters) +public List_t Text$split(Text_t text, Text_t delimiters) { if (delimiters.length == 0) return Text$clusters(text); TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters); - Array_t splits = {}; + List_t splits = {}; for (int64_t i = 0; i < text.length; ) { int64_t span_len = 0; while (i + span_len < text.length && !_matches(&text_state, &delim_state, i + span_len)) { span_len += 1; } Text_t slice = Text$slice(text, I(i+1), I(i+span_len)); - Array$insert(&splits, &slice, I(0), sizeof(slice)); + List$insert(&splits, &slice, I(0), sizeof(slice)); i += span_len + delimiters.length; if (i == text.length) { Text_t empty = Text(""); - Array$insert(&splits, &empty, I(0), sizeof(empty)); + List$insert(&splits, &empty, I(0), sizeof(empty)); } } return splits; } -public Array_t Text$split_any(Text_t text, Text_t delimiters) +public List_t Text$split_any(Text_t text, Text_t delimiters) { if (delimiters.length == 0) - return Array(text); + return List(text); TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters); - Array_t splits = {}; + List_t splits = {}; for (int64_t i = 0; i < text.length; ) { int64_t span_len = 0; while (i + span_len < text.length && !_has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i + span_len))) { @@ -1159,14 +1159,14 @@ public Array_t Text$split_any(Text_t text, Text_t delimiters) } bool trailing_delim = i + span_len < text.length; Text_t slice = Text$slice(text, I(i+1), I(i+span_len)); - Array$insert(&splits, &slice, I(0), sizeof(slice)); + List$insert(&splits, &slice, I(0), sizeof(slice)); i += span_len + 1; while (i < text.length && _has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i))) { i += 1; } if (i >= text.length && trailing_delim) { Text_t empty = Text(""); - Array$insert(&splits, &empty, I(0), sizeof(empty)); + List$insert(&splits, &empty, I(0), sizeof(empty)); } } return splits; @@ -1303,7 +1303,7 @@ PUREFUNC public bool Text$equal_ignoring_case(Text_t a, Text_t b, Text_t languag public Text_t Text$upper(Text_t text, Text_t language) { if (text.length == 0) return text; - Array_t codepoints = Text$utf32_codepoints(text); + List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); ucs4_t buf[128]; size_t out_len = sizeof(buf)/sizeof(buf[0]); @@ -1316,7 +1316,7 @@ public Text_t Text$upper(Text_t text, Text_t language) public Text_t Text$lower(Text_t text, Text_t language) { if (text.length == 0) return text; - Array_t codepoints = Text$utf32_codepoints(text); + List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); ucs4_t buf[128]; size_t out_len = sizeof(buf)/sizeof(buf[0]); @@ -1329,7 +1329,7 @@ public Text_t Text$lower(Text_t text, Text_t language) public Text_t Text$title(Text_t text, Text_t language) { if (text.length == 0) return text; - Array_t codepoints = Text$utf32_codepoints(text); + List_t codepoints = Text$utf32_codepoints(text); const char *uc_language = Text$as_c_string(language); ucs4_t buf[128]; size_t out_len = sizeof(buf)/sizeof(buf[0]); @@ -1451,7 +1451,7 @@ public Text_t Text$as_text(const void *vtext, bool colorize, const TypeInfo_t *i return as_text; } -public Text_t Text$join(Text_t glue, Array_t pieces) +public Text_t Text$join(Text_t glue, List_t pieces) { if (pieces.length == 0) return EMPTY_TEXT; @@ -1478,38 +1478,38 @@ public Text_t Text$format(const char *fmt, ...) return ret; } -public Array_t Text$clusters(Text_t text) +public List_t Text$clusters(Text_t text) { - Array_t clusters = {}; + List_t clusters = {}; for (int64_t i = 1; i <= text.length; i++) { Text_t cluster = Text$slice(text, I(i), I(i)); - Array$insert(&clusters, &cluster, I_small(0), sizeof(Text_t)); + List$insert(&clusters, &cluster, I_small(0), sizeof(Text_t)); } return clusters; } -public Array_t Text$utf32_codepoints(Text_t text) +public List_t Text$utf32_codepoints(Text_t text) { - Array_t codepoints = {.atomic=1}; + List_t codepoints = {.atomic=1}; TextIter_t state = NEW_TEXT_ITER_STATE(text); for (int64_t i = 0; i < text.length; i++) { int32_t grapheme = Text$get_grapheme_fast(&state, i); if (grapheme < 0) { for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) { ucs4_t subg = GRAPHEME_CODEPOINTS(grapheme)[c]; - Array$insert(&codepoints, &subg, I_small(0), sizeof(ucs4_t)); + List$insert(&codepoints, &subg, I_small(0), sizeof(ucs4_t)); } } else { - Array$insert(&codepoints, &grapheme, I_small(0), sizeof(ucs4_t)); + List$insert(&codepoints, &grapheme, I_small(0), sizeof(ucs4_t)); } } return codepoints; } -public Array_t Text$utf8_bytes(Text_t text) +public List_t Text$utf8_bytes(Text_t text) { const char *str = Text$as_c_string(text); - return (Array_t){.length=strlen(str), .stride=1, .atomic=1, .data=(void*)str}; + return (List_t){.length=strlen(str), .stride=1, .atomic=1, .data=(void*)str}; } static INLINE const char *codepoint_name(ucs4_t c) @@ -1523,9 +1523,9 @@ static INLINE const char *codepoint_name(ucs4_t c) return name; } -public Array_t Text$codepoint_names(Text_t text) +public List_t Text$codepoint_names(Text_t text) { - Array_t names = {}; + List_t names = {}; TextIter_t state = NEW_TEXT_ITER_STATE(text); for (int64_t i = 0; i < text.length; i++) { int32_t grapheme = Text$get_grapheme_fast(&state, i); @@ -1533,65 +1533,65 @@ public Array_t Text$codepoint_names(Text_t text) for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) { const char *name = codepoint_name(GRAPHEME_CODEPOINTS(grapheme)[c]); Text_t name_text = Text$from_str(name); - Array$insert(&names, &name_text, I_small(0), sizeof(Text_t)); + List$insert(&names, &name_text, I_small(0), sizeof(Text_t)); } } else { const char *name = codepoint_name((ucs4_t)grapheme); Text_t name_text = Text$from_str(name); - Array$insert(&names, &name_text, I_small(0), sizeof(Text_t)); + List$insert(&names, &name_text, I_small(0), sizeof(Text_t)); } } return names; } -public Text_t Text$from_codepoints(Array_t codepoints) +public Text_t Text$from_codepoints(List_t codepoints) { if (codepoints.stride != sizeof(int32_t)) - Array$compact(&codepoints, sizeof(int32_t)); + List$compact(&codepoints, sizeof(int32_t)); return text_from_u32(codepoints.data, codepoints.length, true); } -public OptionalText_t Text$from_codepoint_names(Array_t codepoint_names) +public OptionalText_t Text$from_codepoint_names(List_t codepoint_names) { - Array_t codepoints = {}; + List_t codepoints = {}; for (int64_t i = 0; i < codepoint_names.length; i++) { Text_t *name = ((Text_t*)(codepoint_names.data + i*codepoint_names.stride)); const char *name_str = Text$as_c_string(*name); ucs4_t codepoint = unicode_name_character(name_str); if (codepoint == UNINAME_INVALID) return NONE_TEXT; - Array$insert(&codepoints, &codepoint, I_small(0), sizeof(ucs4_t)); + List$insert(&codepoints, &codepoint, I_small(0), sizeof(ucs4_t)); } return Text$from_codepoints(codepoints); } -public OptionalText_t Text$from_bytes(Array_t bytes) +public OptionalText_t Text$from_bytes(List_t bytes) { if (bytes.stride != sizeof(int8_t)) - Array$compact(&bytes, sizeof(int8_t)); + List$compact(&bytes, sizeof(int8_t)); return Text$from_strn(bytes.data, (size_t)bytes.length); } -public Array_t Text$lines(Text_t text) +public List_t Text$lines(Text_t text) { - Array_t lines = {}; + List_t lines = {}; TextIter_t state = NEW_TEXT_ITER_STATE(text); for (int64_t i = 0, line_start = 0; i < text.length; i++) { int32_t grapheme = Text$get_grapheme_fast(&state, i); if (grapheme == '\r' && Text$get_grapheme_fast(&state, i + 1) == '\n') { // CRLF Text_t line = Text$slice(text, I(line_start+1), I(i)); - Array$insert(&lines, &line, I_small(0), sizeof(Text_t)); + List$insert(&lines, &line, I_small(0), sizeof(Text_t)); i += 1; // skip one extra for CR line_start = i + 1; } else if (grapheme == '\n') { // newline Text_t line = Text$slice(text, I(line_start+1), I(i)); - Array$insert(&lines, &line, I_small(0), sizeof(Text_t)); + List$insert(&lines, &line, I_small(0), sizeof(Text_t)); line_start = i + 1; } else if (i == text.length-1 && line_start != i) { // last line Text_t line = Text$slice(text, I(line_start+1), I(i+1)); - Array$insert(&lines, &line, I_small(0), sizeof(Text_t)); + List$insert(&lines, &line, I_small(0), sizeof(Text_t)); } } return lines; @@ -1645,7 +1645,7 @@ public void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const fwrite(str, sizeof(char), (size_t)len, out); } -public void Text$deserialize(FILE *in, void *out, Array_t *pointers, const TypeInfo_t *) +public void Text$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *) { int64_t len = -1; Int64$deserialize(in, &len, pointers, &Int64$info); diff --git a/src/stdlib/text.h b/src/stdlib/text.h index 662c6e5f..604cea44 100644 --- a/src/stdlib/text.h +++ b/src/stdlib/text.h @@ -55,24 +55,24 @@ Text_t Text$without_suffix(Text_t text, Text_t suffix); Text_t Text$replace(Text_t text, Text_t target, Text_t replacement); Text_t Text$translate(Text_t text, Table_t translations); bool Text$has(Text_t text, Text_t target); -Array_t Text$split(Text_t text, Text_t delimiter); -Array_t Text$split_any(Text_t text, Text_t delimiters); +List_t Text$split(Text_t text, Text_t delimiter); +List_t Text$split_any(Text_t text, Text_t delimiters); Closure_t Text$by_split(Text_t text, Text_t delimiter); Closure_t Text$by_split_any(Text_t text, Text_t delimiters); Text_t Text$trim(Text_t text, Text_t to_trim, bool left, bool right); char *Text$as_c_string(Text_t text); __attribute__((format(printf, 1, 2))) public Text_t Text$format(const char *fmt, ...); -Array_t Text$clusters(Text_t text); -Array_t Text$utf32_codepoints(Text_t text); -Array_t Text$utf8_bytes(Text_t text); -Array_t Text$codepoint_names(Text_t text); -Text_t Text$from_codepoints(Array_t codepoints); -OptionalText_t Text$from_codepoint_names(Array_t codepoint_names); -OptionalText_t Text$from_bytes(Array_t bytes); -Array_t Text$lines(Text_t text); +List_t Text$clusters(Text_t text); +List_t Text$utf32_codepoints(Text_t text); +List_t Text$utf8_bytes(Text_t text); +List_t Text$codepoint_names(Text_t text); +Text_t Text$from_codepoints(List_t codepoints); +OptionalText_t Text$from_codepoint_names(List_t codepoint_names); +OptionalText_t Text$from_bytes(List_t bytes); +List_t Text$lines(Text_t text); Closure_t Text$by_line(Text_t text); -Text_t Text$join(Text_t glue, Array_t pieces); +Text_t Text$join(Text_t glue, List_t pieces); Text_t Text$repeat(Text_t text, Int_t count); Int_t Text$width(Text_t text, Text_t language); Text_t Text$left_pad(Text_t text, Int_t width, Text_t padding, Text_t language); @@ -81,7 +81,7 @@ Text_t Text$middle_pad(Text_t text, Int_t width, Text_t padding, Text_t language int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index); uint32_t Text$get_main_grapheme_fast(TextIter_t *state, int64_t index); void Text$serialize(const void *obj, FILE *out, Table_t *, const TypeInfo_t *); -void Text$deserialize(FILE *in, void *out, Array_t *, const TypeInfo_t *); +void Text$deserialize(FILE *in, void *out, List_t *, const TypeInfo_t *); MACROLIKE int32_t Text$get_grapheme(Text_t text, int64_t index) { diff --git a/src/stdlib/tomo.h b/src/stdlib/tomo.h index b5642ec5..2d8d9908 100644 --- a/src/stdlib/tomo.h +++ b/src/stdlib/tomo.h @@ -7,7 +7,7 @@ #include #include -#include "arrays.h" +#include "lists.h" #include "bools.h" #include "bytes.h" #include "c_strings.h" diff --git a/src/stdlib/types.c b/src/stdlib/types.c index 8ced9051..0f51d6ea 100644 --- a/src/stdlib/types.c +++ b/src/stdlib/types.c @@ -6,7 +6,7 @@ #include #include "util.h" -#include "arrays.h" +#include "lists.h" #include "pointers.h" #include "tables.h" #include "text.h" diff --git a/src/stdlib/types.h b/src/stdlib/types.h index 786e92d4..ddece7c9 100644 --- a/src/stdlib/types.h +++ b/src/stdlib/types.h @@ -17,7 +17,7 @@ typedef struct { Text_t (*as_text)(const void*, bool, const TypeInfo_t*); bool (*is_none)(const void*, const TypeInfo_t*); void (*serialize)(const void*, FILE*, Table_t*, const TypeInfo_t*); - void (*deserialize)(FILE*, void*, Array_t*, const TypeInfo_t*); + void (*deserialize)(FILE*, void*, List_t*, const TypeInfo_t*); } metamethods_t; typedef struct { @@ -29,7 +29,7 @@ struct TypeInfo_s { int64_t size, align; metamethods_t metamethods; struct { // Anonymous tagged union for convenience - enum { OpaqueInfo, StructInfo, EnumInfo, PointerInfo, TextInfo, ArrayInfo, TableInfo, FunctionInfo, + enum { OpaqueInfo, StructInfo, EnumInfo, PointerInfo, TextInfo, ListInfo, TableInfo, FunctionInfo, OptionalInfo, TypeInfoInfo } tag; union { struct {} OpaqueInfo; @@ -42,7 +42,7 @@ struct TypeInfo_s { } TextInfo; struct { const TypeInfo_t *item; - } ArrayInfo; + } ListInfo; struct { const TypeInfo_t *key, *value; } TableInfo; diff --git a/src/tomo.c b/src/tomo.c index effa74bd..4c10b543 100644 --- a/src/tomo.c +++ b/src/tomo.c @@ -15,7 +15,7 @@ #include "cordhelpers.h" #include "parse.h" #include "repl.h" -#include "stdlib/arrays.h" +#include "stdlib/lists.h" #include "stdlib/bools.h" #include "stdlib/bytes.h" #include "stdlib/datatypes.h" @@ -28,14 +28,14 @@ #include "types.h" #define run_cmd(...) ({ const char *_cmd = String(__VA_ARGS__); if (verbose) print("\033[34;1m", _cmd, "\033[m"); popen(_cmd, "w"); }) -#define array_text(arr) Text$join(Text(" "), arr) +#define list_text(list) Text$join(Text(" "), list) #ifdef __linux__ // Only on Linux is /proc/self/exe available static struct stat compiler_stat; #endif -static const char *paths_str(Array_t paths) { +static const char *paths_str(List_t paths) { Text_t result = EMPTY_TEXT; for (int64_t i = 0; i < paths.length; i++) { if (i > 0) result = Texts(result, Text(" ")); @@ -44,10 +44,10 @@ static const char *paths_str(Array_t paths) { return Text$as_c_string(result); } -static OptionalArray_t files = NONE_ARRAY, - args = NONE_ARRAY, - uninstall = NONE_ARRAY, - libraries = NONE_ARRAY; +static OptionalList_t files = NONE_LIST, + args = NONE_LIST, + uninstall = NONE_LIST, + libraries = NONE_LIST; static OptionalBool_t verbose = false, quiet = false, stop_at_transpile = false, @@ -82,11 +82,11 @@ static const char *SHARED_SUFFIX = static void transpile_header(env_t *base_env, Path_t path); static void transpile_code(env_t *base_env, Path_t path); static void compile_object_file(Path_t path); -static Path_t compile_executable(env_t *base_env, Path_t path, Path_t exe_path, Array_t object_files, Array_t extra_ldlibs); +static Path_t compile_executable(env_t *base_env, Path_t path, Path_t exe_path, List_t object_files, List_t extra_ldlibs); static void build_file_dependency_graph(Path_t path, Table_t *to_compile, Table_t *to_link); static Text_t escape_lib_name(Text_t lib_name); static void build_library(Text_t lib_dir_name); -static void compile_files(env_t *env, Array_t files, Array_t *object_files, Array_t *ldlibs); +static void compile_files(env_t *env, List_t files, List_t *object_files, List_t *ldlibs); static bool is_stale(Path_t path, Path_t relative_to); static Path_t build_file(Path_t path, const char *extension); static void wait_for_child_success(pid_t child); @@ -148,8 +148,8 @@ int main(int argc, char *argv[]) Text_t help = Texts(Text("\x1b[1mtomo\x1b[m: a compiler for the Tomo programming language"), Text("\n\n"), usage); tomo_parse_args( argc, argv, usage, help, - {"files", true, Array$info(&Path$info), &files}, - {"args", true, Array$info(&Text$info), &args}, + {"files", true, List$info(&Path$info), &files}, + {"args", true, List$info(&Text$info), &args}, {"verbose", false, &Bool$info, &verbose}, {"v", false, &Bool$info, &verbose}, {"quiet", false, &Bool$info, &quiet}, @@ -160,10 +160,10 @@ int main(int argc, char *argv[]) {"c", false, &Bool$info, &stop_at_obj_compilation}, {"compile-exe", false, &Bool$info, &compile_exe}, {"e", false, &Bool$info, &compile_exe}, - {"uninstall", false, Array$info(&Text$info), &uninstall}, - {"u", false, Array$info(&Text$info), &uninstall}, - {"library", false, Array$info(&Path$info), &libraries}, - {"L", false, Array$info(&Path$info), &libraries}, + {"uninstall", false, List$info(&Text$info), &uninstall}, + {"u", false, List$info(&Text$info), &uninstall}, + {"library", false, List$info(&Path$info), &libraries}, + {"L", false, List$info(&Path$info), &libraries}, {"show-codegen", false, &Text$info, &show_codegen}, {"C", false, &Text$info, &show_codegen}, {"repl", false, &Bool$info, &run_repl}, @@ -252,7 +252,7 @@ int main(int argc, char *argv[]) pid_t child = fork(); if (child == 0) { env_t *env = global_env(); - Array_t object_files = {}, + List_t object_files = {}, extra_ldlibs = {}; compile_files(env, files, &object_files, &extra_ldlibs); compile_executable(env, path, exe_path, object_files, extra_ldlibs); @@ -407,9 +407,9 @@ static void _compile_file_header_for_library(env_t *env, Path_t header_path, Pat void build_library(Text_t lib_dir_name) { - Array_t tm_files = Path$glob(Path("./[!._0-9]*.tm")); + List_t tm_files = Path$glob(Path("./[!._0-9]*.tm")); env_t *env = fresh_scope(global_env()); - Array_t object_files = {}, + List_t object_files = {}, extra_ldlibs = {}; // Resolve all files to absolute paths: @@ -455,7 +455,7 @@ void build_library(Text_t lib_dir_name) errx(WEXITSTATUS(status), "Failed to create symbol rename table with `nm` and `sed`"); } - prog = run_cmd(cc, " -O", optimization, " ", cflags, " ", ldflags, " ", ldlibs, " ", array_text(extra_ldlibs), + prog = run_cmd(cc, " -O", optimization, " ", cflags, " ", ldflags, " ", ldlibs, " ", list_text(extra_ldlibs), #ifdef __APPLE__ " -Wl,-install_name,@rpath/'lib", lib_dir_name, SHARED_SUFFIX, "'" #else @@ -501,7 +501,7 @@ void build_library(Text_t lib_dir_name) } } -void compile_files(env_t *env, Array_t to_compile, Array_t *object_files, Array_t *extra_ldlibs) +void compile_files(env_t *env, List_t to_compile, List_t *object_files, List_t *extra_ldlibs) { Table_t to_link = {}; Table_t dependency_files = {}; @@ -562,13 +562,13 @@ void compile_files(env_t *env, Array_t to_compile, Array_t *object_files, Array_ for (int64_t i = 0; i < dependency_files.entries.length; i++) { Path_t path = *(Path_t*)(dependency_files.entries.data + i*dependency_files.entries.stride); path = build_file(path, ".o"); - Array$insert(object_files, &path, I(0), sizeof(Path_t)); + List$insert(object_files, &path, I(0), sizeof(Path_t)); } } if (extra_ldlibs) { for (int64_t i = 0; i < to_link.entries.length; i++) { Text_t lib = *(Text_t*)(to_link.entries.data + i*to_link.entries.stride); - Array$insert(extra_ldlibs, &lib, I(0), sizeof(Text_t)); + List$insert(extra_ldlibs, &lib, I(0), sizeof(Text_t)); } } } @@ -615,7 +615,7 @@ void build_file_dependency_graph(Path_t path, Table_t *to_compile, Table_t *to_l Text_t lib = Text$format("'%s/.local/share/tomo/installed/%s/lib%s%s'", getenv("HOME"), use->path, use->path, SHARED_SUFFIX); Table$set(to_link, &lib, ((Bool_t[1]){1}), Table$info(&Text$info, &Bool$info)); - Array_t children = Path$glob(Path$from_str(String(getenv("HOME"), "/.local/share/tomo/installed/", use->path, "/*.tm"))); + List_t children = Path$glob(Path$from_str(String(getenv("HOME"), "/.local/share/tomo/installed/", use->path, "/*.tm"))); for (int64_t i = 0; i < children.length; i++) { Path_t *child = (Path_t*)(children.data + i*children.stride); Table_t discarded = {.fallback=to_compile}; @@ -745,7 +745,7 @@ void compile_object_file(Path_t path) print("Compiled object:\t", obj_file); } -Path_t compile_executable(env_t *base_env, Path_t path, Path_t exe_path, Array_t object_files, Array_t extra_ldlibs) +Path_t compile_executable(env_t *base_env, Path_t path, Path_t exe_path, List_t object_files, List_t extra_ldlibs) { ast_t *ast = parse_file(Path$as_c_string(path), NULL); if (!ast) @@ -755,7 +755,7 @@ Path_t compile_executable(env_t *base_env, Path_t path, Path_t exe_path, Array_t if (!main_binding || main_binding->type->tag != FunctionType) print_err("No main() function has been defined for ", path, ", so it can't be run!"); - FILE *runner = run_cmd(cc, " ", cflags, " -O", optimization, " ", ldflags, " ", ldlibs, " ", array_text(extra_ldlibs), " ", + FILE *runner = run_cmd(cc, " ", cflags, " -O", optimization, " ", ldflags, " ", ldlibs, " ", list_text(extra_ldlibs), " ", paths_str(object_files), " -x c - -o ", exe_path); CORD program = CORD_all( "extern int ", main_binding->code, "$parse_and_run(int argc, char *argv[]);\n" diff --git a/src/typecheck.c b/src/typecheck.c index a869f73e..ce8b4276 100644 --- a/src/typecheck.c +++ b/src/typecheck.c @@ -52,26 +52,26 @@ type_t *parse_type_ast(env_t *env, type_ast_t *ast) code_err(ast, "Void pointers are not supported. You probably meant 'Memory' instead of 'Void'"); return Type(PointerType, .pointed=pointed_t, .is_stack=ptr->is_stack); } - case ArrayTypeAST: { - type_ast_t *item_type = Match(ast, ArrayTypeAST)->item; + case ListTypeAST: { + type_ast_t *item_type = Match(ast, ListTypeAST)->item; type_t *item_t = parse_type_ast(env, item_type); if (!item_t) code_err(item_type, "I can't figure out what this type is."); if (has_stack_memory(item_t)) - code_err(item_type, "Arrays can't have stack references because the array may outlive the stack frame."); - if (type_size(item_t) > ARRAY_MAX_STRIDE) - code_err(ast, "This array holds items that take up ", (uint64_t)type_size(item_t), - " bytes, but the maximum supported size is ", ARRAY_MAX_STRIDE, " bytes. Consider using an array of pointers instead."); - return Type(ArrayType, .item_type=item_t); + code_err(item_type, "Lists can't have stack references because the list may outlive the stack frame."); + if (type_size(item_t) > LIST_MAX_STRIDE) + code_err(ast, "This list holds items that take up ", (uint64_t)type_size(item_t), + " bytes, but the maximum supported size is ", LIST_MAX_STRIDE, " bytes. Consider using a list of pointers instead."); + return Type(ListType, .item_type=item_t); } case SetTypeAST: { type_ast_t *item_type = Match(ast, SetTypeAST)->item; type_t *item_t = parse_type_ast(env, item_type); if (!item_t) code_err(item_type, "I can't figure out what this type is."); if (has_stack_memory(item_t)) - code_err(item_type, "Sets can't have stack references because the array may outlive the stack frame."); - if (type_size(item_t) > ARRAY_MAX_STRIDE) + code_err(item_type, "Sets can't have stack references because the list may outlive the stack frame."); + if (type_size(item_t) > LIST_MAX_STRIDE) code_err(ast, "This set holds items that take up ", (uint64_t)type_size(item_t), - " bytes, but the maximum supported size is ", ARRAY_MAX_STRIDE, " bytes. Consider using an set of pointers instead."); + " bytes, but the maximum supported size is ", LIST_MAX_STRIDE, " bytes. Consider using an set of pointers instead."); return Type(SetType, .item_type=item_t); } case TableTypeAST: { @@ -80,12 +80,12 @@ type_t *parse_type_ast(env_t *env, type_ast_t *ast) type_t *key_type = parse_type_ast(env, key_type_ast); if (!key_type) code_err(key_type_ast, "I can't figure out what type this is."); if (has_stack_memory(key_type)) - code_err(key_type_ast, "Tables can't have stack references because the array may outlive the stack frame."); + code_err(key_type_ast, "Tables can't have stack references because the list may outlive the stack frame."); type_t *val_type = parse_type_ast(env, table_type->value); if (!val_type) code_err(table_type->value, "I can't figure out what type this is."); if (has_stack_memory(val_type)) - code_err(table_type->value, "Tables can't have stack references because the array may outlive the stack frame."); + code_err(table_type->value, "Tables can't have stack references because the list may outlive the stack frame."); else if (val_type->tag == OptionalType) code_err(ast, "Tables with optional-typed values are not currently supported"); @@ -273,7 +273,7 @@ void prebind_statement(env_t *env, ast_t *statement) extended->libname = env->libname; for (ast_list_t *stmt = extend->body ? Match(extend->body, Block)->statements : NULL; stmt; stmt = stmt->next) prebind_statement(extended, stmt->ast); - Array_t new_bindings = extended->locals->entries; + List_t new_bindings = extended->locals->entries; for (int64_t i = 0; i < new_bindings.length; i++) { struct { const char *name; binding_t *binding; } *entry = new_bindings.data + i*new_bindings.stride; binding_t *clobbered = Table$str_get(*ns_env->locals, entry->name); @@ -334,7 +334,7 @@ void bind_statement(env_t *env, ast_t *statement) get_line_number(statement->file, statement->start)); binding_t binding = {.type=type, .code=code}; env_t *type_ns = get_namespace_by_type(env, ret_t); - Array$insert(&type_ns->namespace->constructors, &binding, I(0), sizeof(binding)); + List$insert(&type_ns->namespace->constructors, &binding, I(0), sizeof(binding)); break; } case StructDef: { @@ -461,7 +461,7 @@ void bind_statement(env_t *env, ast_t *statement) extended->libname = env->libname; for (ast_list_t *stmt = extend->body ? Match(extend->body, Block)->statements : NULL; stmt; stmt = stmt->next) bind_statement(extended, stmt->ast); - Array_t new_bindings = extended->locals->entries; + List_t new_bindings = extended->locals->entries; for (int64_t i = 0; i < new_bindings.length; i++) { struct { const char *name; binding_t *binding; } *entry = new_bindings.data + i*new_bindings.stride; binding_t *clobbered = Table$str_get(*ns_env->locals, entry->name); @@ -660,7 +660,7 @@ type_t *get_type(env_t *env, ast_t *ast) code_err(ast, "'&' stack references can only be used on the fields of pointers and local variables"); } case Index: - code_err(ast, "'&' stack references are not supported for array or table indexing"); + code_err(ast, "'&' stack references are not supported for list or table indexing"); default: return Type(PointerType, .pointed=get_type(env, value), .is_stack=true); } @@ -698,10 +698,10 @@ type_t *get_type(env_t *env, ast_t *ast) if (b) return b->type; code_err(ast, "I don't know what ", quoted(var->name), " refers to"); } - case Array: { - auto array = Match(ast, Array); + case List: { + auto list = Match(ast, List); type_t *item_type = NULL; - for (ast_list_t *item = array->items; item; item = item->next) { + for (ast_list_t *item = list->items; item; item = item->next) { ast_t *item_ast = item->ast; env_t *scope = env; while (item_ast->tag == Comprehension) { @@ -714,15 +714,15 @@ type_t *get_type(env_t *env, ast_t *ast) type_t *merged = item_type ? type_or_type(item_type, t2) : t2; if (!merged) code_err(item->ast, - "This array item has type ", type_to_str(t2), - ", which is different from earlier array items which have type ", type_to_str(item_type)); + "This list item has type ", type_to_str(t2), + ", which is different from earlier list items which have type ", type_to_str(item_type)); item_type = merged; } if (item_type && has_stack_memory(item_type)) - code_err(ast, "Arrays cannot hold stack references, because the array may outlive the stack frame the reference was created in."); + code_err(ast, "Lists cannot hold stack references, because the list may outlive the stack frame the reference was created in."); - return Type(ArrayType, .item_type=item_type); + return Type(ListType, .item_type=item_type); } case Set: { auto set = Match(ast, Set); @@ -800,7 +800,7 @@ type_t *get_type(env_t *env, ast_t *ast) auto e = Match(comp->expr, TableEntry); return Type(TableType, .key_type=get_type(scope, e->key), .value_type=get_type(scope, e->value), .env=env); } else { - return Type(ArrayType, .item_type=get_type(scope, comp->expr)); + return Type(ListType, .item_type=get_type(scope, comp->expr)); } } case FieldAccess: { @@ -833,11 +833,11 @@ type_t *get_type(env_t *env, ast_t *ast) return Match(indexed_t, PointerType)->pointed; type_t *value_t = value_type(indexed_t); - if (value_t->tag == ArrayType) { + if (value_t->tag == ListType) { if (!indexing->index) return indexed_t; type_t *index_t = get_type(env, indexing->index); if (index_t->tag == IntType || index_t->tag == BigIntType || index_t->tag == ByteType) - return Match(value_t, ArrayType)->item_type; + return Match(value_t, ListType)->item_type; code_err(indexing->index, "I only know how to index lists using integers, not ", type_to_str(index_t)); } else if (value_t->tag == TableType) { auto table_type = Match(value_t, TableType); @@ -878,7 +878,7 @@ type_t *get_type(env_t *env, ast_t *ast) auto call = Match(ast, MethodCall); if (streq(call->name, "serialized")) // Data serialization - return Type(ArrayType, Type(ByteType)); + return Type(ListType, Type(ByteType)); type_t *self_value_t = get_type(env, call->self); if (!self_value_t) code_err(call->self, "Couldn't get the type of this value"); @@ -890,8 +890,8 @@ type_t *get_type(env_t *env, ast_t *ast) } switch (self_value_t->tag) { - case ArrayType: { - type_t *item_type = Match(self_value_t, ArrayType)->item_type; + case ListType: { + type_t *item_type = Match(self_value_t, ListType)->item_type; if (streq(call->name, "binary_search")) return INT_TYPE; else if (streq(call->name, "by")) return self_value_t; else if (streq(call->name, "clear")) return Type(VoidType); @@ -918,7 +918,7 @@ type_t *get_type(env_t *env, ast_t *ast) else if (streq(call->name, "sorted")) return self_value_t; else if (streq(call->name, "to")) return self_value_t; else if (streq(call->name, "unique")) return Type(SetType, .item_type=item_type); - else code_err(ast, "There is no '", call->name, "' method for arrays"); + else code_err(ast, "There is no '", call->name, "' method for lists"); } case SetType: { if (streq(call->name, "add")) return Type(VoidType); @@ -1266,7 +1266,7 @@ type_t *get_type(env_t *env, ast_t *ast) binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, overall_t); if (b) return overall_t; - if (overall_t->tag == ArrayType || overall_t->tag == SetType || overall_t->tag == TextType) + if (overall_t->tag == ListType || overall_t->tag == SetType || overall_t->tag == TextType) return overall_t; code_err(ast, "I don't know how to do concatenation between ", type_to_str(lhs_t), " and ", type_to_str(rhs_t)); @@ -1680,9 +1680,9 @@ PUREFUNC bool can_compile_to_type(env_t *env, ast_t *ast, type_t *needed) return true; needed = non_optional(needed); - if (needed->tag == ArrayType && ast->tag == Array) { - type_t *item_type = Match(needed, ArrayType)->item_type; - for (ast_list_t *item = Match(ast, Array)->items; item; item = item->next) { + if (needed->tag == ListType && ast->tag == List) { + type_t *item_type = Match(needed, ListType)->item_type; + for (ast_list_t *item = Match(ast, List)->items; item; item = item->next) { if (!can_compile_to_type(env, item->ast, item_type)) return false; } diff --git a/src/types.c b/src/types.c index 0433cc48..83c3e702 100644 --- a/src/types.c +++ b/src/types.c @@ -33,9 +33,9 @@ CORD type_to_cord(type_t *t) { case BigIntType: return "Int"; case IntType: return CORD_asprintf("Int%d", Match(t, IntType)->bits); case NumType: return Match(t, NumType)->bits == TYPE_NBITS32 ? "Num32" : "Num"; - case ArrayType: { - auto array = Match(t, ArrayType); - return CORD_asprintf("[%r]", type_to_cord(array->item_type)); + case ListType: { + auto list = Match(t, ListType); + return CORD_asprintf("[%r]", type_to_cord(list->item_type)); } case TableType: { auto table = Match(t, TableType); @@ -240,7 +240,7 @@ PUREFUNC precision_cmp_e compare_precision(type_t *a, type_t *b) PUREFUNC bool has_heap_memory(type_t *t) { switch (t->tag) { - case ArrayType: return true; + case ListType: return true; case TableType: return true; case SetType: return true; case PointerType: return true; @@ -367,7 +367,7 @@ PUREFUNC bool can_promote(type_t *actual, type_t *needed) } // Empty literals: - if (actual->tag == ArrayType && needed->tag == ArrayType && Match(actual, ArrayType)->item_type == NULL) + if (actual->tag == ListType && needed->tag == ListType && Match(actual, ListType)->item_type == NULL) return true; // [] -> [T] if (actual->tag == SetType && needed->tag == SetType && Match(actual, SetType)->item_type == NULL) return true; // || -> |T| @@ -410,9 +410,9 @@ PUREFUNC bool can_promote(type_t *actual, type_t *needed) && can_promote(actual_ret, needed_ret))); } - // Set -> Array promotion - if (needed->tag == ArrayType && actual->tag == SetType - && type_eq(Match(needed, ArrayType)->item_type, Match(actual, SetType)->item_type)) + // Set -> List promotion + if (needed->tag == ListType && actual->tag == SetType + && type_eq(Match(needed, ListType)->item_type, Match(actual, SetType)->item_type)) return true; return false; @@ -508,7 +508,7 @@ PUREFUNC size_t type_size(type_t *t) } case NumType: return Match(t, NumType)->bits == TYPE_NBITS64 ? sizeof(double) : sizeof(float); case TextType: return sizeof(Text_t); - case ArrayType: return sizeof(Array_t); + case ListType: return sizeof(List_t); case SetType: return sizeof(Table_t); case TableType: return sizeof(Table_t); case FunctionType: return sizeof(void*); @@ -599,7 +599,7 @@ PUREFUNC size_t type_align(type_t *t) case NumType: return Match(t, NumType)->bits == TYPE_NBITS64 ? __alignof__(double) : __alignof__(float); case TextType: return __alignof__(Text_t); case SetType: return __alignof__(Table_t); - case ArrayType: return __alignof__(Array_t); + case ListType: return __alignof__(List_t); case TableType: return __alignof__(Table_t); case FunctionType: return __alignof__(void*); case ClosureType: return __alignof__(struct {void *fn, *userdata;}); @@ -680,21 +680,21 @@ type_t *get_field_type(type_t *t, const char *field_name) if (streq(field_name, "length")) return INT_TYPE; else if (streq(field_name, "items")) - return Type(ArrayType, .item_type=Match(t, SetType)->item_type); + return Type(ListType, .item_type=Match(t, SetType)->item_type); return NULL; } case TableType: { if (streq(field_name, "length")) return INT_TYPE; else if (streq(field_name, "keys")) - return Type(ArrayType, Match(t, TableType)->key_type); + return Type(ListType, Match(t, TableType)->key_type); else if (streq(field_name, "values")) - return Type(ArrayType, Match(t, TableType)->value_type); + return Type(ListType, Match(t, TableType)->value_type); else if (streq(field_name, "fallback")) return Type(OptionalType, .type=t); return NULL; } - case ArrayType: { + case ListType: { if (streq(field_name, "length")) return INT_TYPE; return NULL; } @@ -707,7 +707,7 @@ PUREFUNC type_t *get_iterated_type(type_t *t) type_t *iter_value_t = value_type(t); switch (iter_value_t->tag) { case BigIntType: case IntType: return iter_value_t; break; - case ArrayType: return Match(iter_value_t, ArrayType)->item_type; break; + case ListType: return Match(iter_value_t, ListType)->item_type; break; case SetType: return Match(iter_value_t, SetType)->item_type; break; case TableType: return NULL; case FunctionType: case ClosureType: { @@ -728,7 +728,7 @@ CONSTFUNC bool is_incomplete_type(type_t *t) switch (t->tag) { case ReturnType: return is_incomplete_type(Match(t, ReturnType)->ret); case OptionalType: return is_incomplete_type(Match(t, OptionalType)->type); - case ArrayType: return is_incomplete_type(Match(t, ArrayType)->item_type); + case ListType: return is_incomplete_type(Match(t, ListType)->item_type); case SetType: return is_incomplete_type(Match(t, SetType)->item_type); case TableType: { auto table = Match(t, TableType); @@ -770,9 +770,9 @@ CONSTFUNC type_t *most_complete_type(type_t *t1, type_t *t2) type_t *opt = most_complete_type(Match(t1, OptionalType)->type, Match(t2, OptionalType)->type); return opt ? Type(OptionalType, opt) : NULL; } - case ArrayType: { - type_t *item = most_complete_type(Match(t1, ArrayType)->item_type, Match(t2, ArrayType)->item_type); - return item ? Type(ArrayType, item) : NULL; + case ListType: { + type_t *item = most_complete_type(Match(t1, ListType)->item_type, Match(t2, ListType)->item_type); + return item ? Type(ListType, item) : NULL; } case SetType: { type_t *item = most_complete_type(Match(t1, SetType)->item_type, Match(t2, SetType)->item_type); diff --git a/src/types.h b/src/types.h index 2d2bd2a3..33e54ff5 100644 --- a/src/types.h +++ b/src/types.h @@ -47,7 +47,7 @@ struct type_s { NumType, CStringType, TextType, - ArrayType, + ListType, SetType, TableType, FunctionType, @@ -81,7 +81,7 @@ struct type_s { } TextType; struct { type_t *item_type; - } ArrayType; + } ListType; struct { type_t *item_type; } SetType; -- cgit v1.2.3