lists.c - tomo

(272 lines)
   1 // This file defines how to compile lists
   2 
   3 #include <gc.h>
   4 #include <glob.h>
   5 #include <gmp.h>
   6 #include <uninorm.h>
   7 
   8 #include "../ast.h"
   9 #include "../config.h"
  10 #include "../environment.h"
  11 #include "../stdlib/text.h"
  12 #include "../stdlib/util.h"
  13 #include "../typecheck.h"
  14 #include "compilation.h"
  15 
  16 static ast_t *add_to_list_comprehension(ast_t *item, ast_t *subject) {
  17     return WrapAST(item, MethodCall, .name = "insert", .self = subject, .args = new (arg_ast_t, .value = item));
  18 }
  19 
  20 public
  21 Text_t compile_typed_list(env_t *env, ast_t *ast, type_t *list_type) {
  22     DeclareMatch(list, ast, List);
  23     if (!list->items) return Text("EMPTY_LIST");
  24 
  25     type_t *item_type = Match(list_type, ListType)->item_type;
  26     if (item_type == NULL) code_err(ast, "I couldn't figure out what item type goes into this list");
  27 
  28     int64_t n = 0;
  29     for (ast_list_t *item = list->items; item; item = item->next) {
  30         ++n;
  31         if (item->ast->tag == Comprehension) goto list_comprehension;
  32     }
  33 
  34     {
  35         env_t *scope = item_type->tag == EnumType ? with_enum_scope(env, item_type) : env;
  36         if (is_incomplete_type(item_type)) code_err(ast, "This list's type can't be inferred!");
  37         Text_t code = Texts("TypedListN(", compile_type(item_type), ", ", n);
  38         for (ast_list_t *item = list->items; item; item = item->next) {
  39             code = Texts(code, ", ", compile_to_type(scope, item->ast, item_type));
  40         }
  41         return Texts(code, ")");
  42     }
  43 
  44 list_comprehension: {
  45     env_t *scope = item_type->tag == EnumType ? with_enum_scope(env, item_type) : fresh_scope(env);
  46     static int64_t comp_num = 1;
  47     const char *comprehension_name = String("list$", comp_num++);
  48     ast_t *comprehension_var =
  49         LiteralCode(Texts("&", comprehension_name), .type = Type(PointerType, .pointed = list_type, .is_stack = true));
  50     Closure_t comp_action = {.fn = add_to_list_comprehension, .userdata = comprehension_var};
  51     scope->comprehension_action = &comp_action;
  52     Text_t code = Texts("({ List_t ", comprehension_name, " = EMPTY_LIST;");
  53     // set_binding(scope, comprehension_name, list_type, comprehension_name);
  54     for (ast_list_t *item = list->items; item; item = item->next) {
  55         if (item->ast->tag == Comprehension) code = Texts(code, "\n", compile_statement(scope, item->ast));
  56         else code = Texts(code, compile_statement(scope, add_to_list_comprehension(item->ast, comprehension_var)));
  57     }
  58     code = Texts(code, " ", comprehension_name, "; })");
  59     return code;
  60 }
  61 }
  62 
  63 public
  64 Text_t compile_list_method_call(env_t *env, ast_t *ast) {
  65     DeclareMatch(call, ast, MethodCall);
  66     type_t *self_t = get_type(env, call->self);
  67 
  68     int64_t pointer_depth = 0;
  69     type_t *self_value_t = self_t;
  70     for (; self_value_t->tag == PointerType; self_value_t = Match(self_value_t, PointerType)->pointed)
  71         pointer_depth += 1;
  72 
  73     Text_t self = compile(env, call->self);
  74 #define EXPECT_POINTER()                                                                                               \
  75     do {                                                                                                               \
  76         if (pointer_depth < 1) code_err(call->self, "I expected a list pointer here, not a list value");               \
  77         else if (pointer_depth > 1) code_err(call->self, "I expected a list pointer here, not a nested list pointer"); \
  78     } while (0)
  79     type_t *item_t = Match(self_value_t, ListType)->item_type;
  80     Text_t padded_item_size = Texts("sizeof(", compile_type(item_t), ")");
  81 
  82     if (streq(call->name, "insert")) {
  83         EXPECT_POINTER();
  84         arg_t *arg_spec =
  85             new (arg_t, .name = "item", .type = item_t,
  86                  .next = new (arg_t, .name = "at", .type = INT_TYPE, .default_val = FakeAST(Int, .str = "0")));
  87         return Texts("List$insert_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
  88                      padded_item_size, ")");
  89     } else if (streq(call->name, "insert_all")) {
  90         EXPECT_POINTER();
  91         arg_t *arg_spec =
  92             new (arg_t, .name = "items", .type = self_value_t,
  93                  .next = new (arg_t, .name = "at", .type = INT_TYPE, .default_val = FakeAST(Int, .str = "0")));
  94         return Texts("List$insert_all(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
  95                      padded_item_size, ")");
  96     } else if (streq(call->name, "remove_at")) {
  97         EXPECT_POINTER();
  98         arg_t *arg_spec =
  99             new (arg_t, .name = "index", .type = INT_TYPE, .default_val = FakeAST(Int, .str = "-1"),
 100                  .next = new (arg_t, .name = "count", .type = INT_TYPE, .default_val = FakeAST(Int, .str = "1")));
 101         return Texts("List$remove_at(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 102                      padded_item_size, ")");
 103     } else if (streq(call->name, "remove_item")) {
 104         EXPECT_POINTER();
 105         arg_t *arg_spec =
 106             new (arg_t, .name = "item", .type = item_t,
 107                  .next = new (arg_t, .name = "max_count", .type = INT_TYPE, .default_val = FakeAST(Int, .str = "-1")));
 108         return Texts("List$remove_item_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 109                      compile_type_info(self_value_t), ")");
 110     } else if (streq(call->name, "has")) {
 111         self = compile_to_pointer_depth(env, call->self, 0, false);
 112         arg_t *arg_spec = new (arg_t, .name = "item", .type = item_t);
 113         return Texts("List$has_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 114                      compile_type_info(self_value_t), ")");
 115     } else if (streq(call->name, "sample")) {
 116         type_t *random_num_type = parse_type_string(env, "func(->Num)?");
 117         self = compile_to_pointer_depth(env, call->self, 0, false);
 118         arg_t *arg_spec =
 119             new (arg_t, .name = "count", .type = INT_TYPE,
 120                  .next = new (
 121                      arg_t, .name = "weights", .type = Type(ListType, .item_type = Type(NumType, .bits = TYPE_NBITS64)),
 122                      .default_val = FakeAST(None),
 123                      .next = new (arg_t, .name = "random", .type = random_num_type, .default_val = FakeAST(None))));
 124         return Texts("List$sample(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 125                      padded_item_size, ")");
 126     } else if (streq(call->name, "shuffle")) {
 127         type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?");
 128         EXPECT_POINTER();
 129         arg_t *arg_spec = new (arg_t, .name = "random", .type = random_int64_type, .default_val = FakeAST(None));
 130         return Texts("List$shuffle(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 131                      padded_item_size, ")");
 132     } else if (streq(call->name, "shuffled")) {
 133         type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?");
 134         self = compile_to_pointer_depth(env, call->self, 0, false);
 135         arg_t *arg_spec = new (arg_t, .name = "random", .type = random_int64_type, .default_val = FakeAST(None));
 136         return Texts("List$shuffled(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 137                      padded_item_size, ")");
 138     } else if (streq(call->name, "random")) {
 139         type_t *random_int64_type = parse_type_string(env, "func(min,max:Int64->Int64)?");
 140         self = compile_to_pointer_depth(env, call->self, 0, false);
 141         arg_t *arg_spec = new (arg_t, .name = "random", .type = random_int64_type, .default_val = FakeAST(None));
 142         return Texts("List$random_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 143                      compile_type(item_t), ", _, ", promote_to_optional(item_t, Text("_")), ", ", compile_none(item_t),
 144                      ")");
 145     } else if (streq(call->name, "sort") || streq(call->name, "sorted")) {
 146         if (streq(call->name, "sort")) EXPECT_POINTER();
 147         else self = compile_to_pointer_depth(env, call->self, 0, false);
 148         Text_t comparison;
 149         if (call->args) {
 150             type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 151             type_t *fn_t = NewFunctionType(Type(IntType, .bits = TYPE_IBITS32), {.name = "x", .type = item_ptr},
 152                                            {.name = "y", .type = item_ptr});
 153             arg_t *arg_spec = new (arg_t, .name = "by", .type = Type(ClosureType, .fn = fn_t));
 154             comparison = compile_arguments(env, ast, arg_spec, call->args);
 155         } else {
 156             comparison = Texts("((Closure_t){.fn=generic_compare, "
 157                                ".userdata=(void*)",
 158                                compile_type_info(item_t), "})");
 159         }
 160         return Texts("List$", call->name, "(", self, ", ", comparison, ", ", padded_item_size, ")");
 161     } else if (streq(call->name, "heapify")) {
 162         EXPECT_POINTER();
 163         Text_t comparison;
 164         if (call->args) {
 165             type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 166             type_t *fn_t = NewFunctionType(Type(IntType, .bits = TYPE_IBITS32), {.name = "x", .type = item_ptr},
 167                                            {.name = "y", .type = item_ptr});
 168             arg_t *arg_spec = new (arg_t, .name = "by", .type = Type(ClosureType, .fn = fn_t));
 169             comparison = compile_arguments(env, ast, arg_spec, call->args);
 170         } else {
 171             comparison = Texts("((Closure_t){.fn=generic_compare, "
 172                                ".userdata=(void*)",
 173                                compile_type_info(item_t), "})");
 174         }
 175         return Texts("List$heapify(", self, ", ", comparison, ", ", padded_item_size, ")");
 176     } else if (streq(call->name, "heap_push")) {
 177         EXPECT_POINTER();
 178         type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 179         type_t *fn_t = NewFunctionType(Type(IntType, .bits = TYPE_IBITS32), {.name = "x", .type = item_ptr},
 180                                        {.name = "y", .type = item_ptr});
 181         ast_t *default_cmp = LiteralCode(Texts("((Closure_t){.fn=generic_compare, "
 182                                                ".userdata=(void*)",
 183                                                compile_type_info(item_t), "})"),
 184                                          .type = Type(ClosureType, .fn = fn_t));
 185         arg_t *arg_spec =
 186             new (arg_t, .name = "item", .type = item_t,
 187                  .next = new (arg_t, .name = "by", .type = Type(ClosureType, .fn = fn_t), .default_val = default_cmp));
 188         Text_t arg_code = compile_arguments(env, ast, arg_spec, call->args);
 189         return Texts("List$heap_push_value(", self, ", ", arg_code, ", ", padded_item_size, ")");
 190     } else if (streq(call->name, "heap_pop")) {
 191         EXPECT_POINTER();
 192         type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 193         type_t *fn_t = NewFunctionType(Type(IntType, .bits = TYPE_IBITS32), {.name = "x", .type = item_ptr},
 194                                        {.name = "y", .type = item_ptr});
 195         ast_t *default_cmp = LiteralCode(Texts("((Closure_t){.fn=generic_compare, "
 196                                                ".userdata=(void*)",
 197                                                compile_type_info(item_t), "})"),
 198                                          .type = Type(ClosureType, .fn = fn_t));
 199         arg_t *arg_spec = new (arg_t, .name = "by", .type = Type(ClosureType, .fn = fn_t), .default_val = default_cmp);
 200         Text_t arg_code = compile_arguments(env, ast, arg_spec, call->args);
 201         return Texts("List$heap_pop_value(", self, ", ", arg_code, ", ", compile_type(item_t), ", _, ",
 202                      promote_to_optional(item_t, Text("_")), ", ", compile_none(item_t), ")");
 203     } else if (streq(call->name, "binary_search")) {
 204         self = compile_to_pointer_depth(env, call->self, 0, call->args != NULL);
 205         type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 206         type_t *fn_t = NewFunctionType(Type(IntType, .bits = TYPE_IBITS32), {.name = "x", .type = item_ptr},
 207                                        {.name = "y", .type = item_ptr});
 208         ast_t *default_cmp = LiteralCode(Texts("((Closure_t){.fn=generic_compare, "
 209                                                ".userdata=(void*)",
 210                                                compile_type_info(item_t), "})"),
 211                                          .type = Type(ClosureType, .fn = fn_t));
 212         arg_t *arg_spec =
 213             new (arg_t, .name = "target", .type = item_t,
 214                  .next = new (arg_t, .name = "by", .type = Type(ClosureType, .fn = fn_t), .default_val = default_cmp));
 215         Text_t arg_code = compile_arguments(env, ast, arg_spec, call->args);
 216         return Texts("List$binary_search_value(", self, ", ", arg_code, ")");
 217     } else if (streq(call->name, "clear")) {
 218         EXPECT_POINTER();
 219         (void)compile_arguments(env, ast, NULL, call->args);
 220         return Texts("List$clear(", self, ")");
 221     } else if (streq(call->name, "find")) {
 222         self = compile_to_pointer_depth(env, call->self, 0, false);
 223         arg_t *arg_spec = new (arg_t, .name = "item", .type = item_t);
 224         return Texts("List$find_value(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ",
 225                      compile_type_info(self_value_t), ")");
 226     } else if (streq(call->name, "where")) {
 227         self = compile_to_pointer_depth(env, call->self, 0, call->args != NULL);
 228         type_t *item_ptr = Type(PointerType, .pointed = item_t, .is_stack = true);
 229         type_t *predicate_type =
 230             Type(ClosureType, .fn = NewFunctionType(Type(BoolType), {.name = "item", .type = item_ptr}));
 231         arg_t *arg_spec = new (arg_t, .name = "predicate", .type = predicate_type);
 232         return Texts("List$first(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")");
 233     } else if (streq(call->name, "from")) {
 234         self = compile_to_pointer_depth(env, call->self, 0, true);
 235         arg_t *arg_spec = new (arg_t, .name = "first", .type = INT_TYPE);
 236         return Texts("List$from(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")");
 237     } else if (streq(call->name, "to")) {
 238         self = compile_to_pointer_depth(env, call->self, 0, true);
 239         arg_t *arg_spec = new (arg_t, .name = "last", .type = INT_TYPE);
 240         return Texts("List$to(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")");
 241     } else if (streq(call->name, "slice")) {
 242         self = compile_to_pointer_depth(env, call->self, 0, true);
 243         arg_t *arg_spec =
 244             new (arg_t, .name = "first", .type = INT_TYPE, .next = new (arg_t, .name = "last", .type = INT_TYPE));
 245         return Texts("List$slice(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ")");
 246     } else if (streq(call->name, "by")) {
 247         self = compile_to_pointer_depth(env, call->self, 0, true);
 248         arg_t *arg_spec = new (arg_t, .name = "stride", .type = INT_TYPE);
 249         return Texts("List$by(", self, ", ", compile_arguments(env, ast, arg_spec, call->args), ", ", padded_item_size,
 250                      ")");
 251     } else if (streq(call->name, "reversed")) {
 252         self = compile_to_pointer_depth(env, call->self, 0, true);
 253         (void)compile_arguments(env, ast, NULL, call->args);
 254         return Texts("List$reversed(", self, ", ", padded_item_size, ")");
 255     } else if (streq(call->name, "unique")) {
 256         self = compile_to_pointer_depth(env, call->self, 0, false);
 257         (void)compile_arguments(env, ast, NULL, call->args);
 258         return Texts("Table$from_entries(", self, ", Table$info(", compile_type_info(item_t), ", &Present$$info))");
 259     } else if (streq(call->name, "pop")) {
 260         EXPECT_POINTER();
 261         arg_t *arg_spec = new (arg_t, .name = "index", .type = INT_TYPE, .default_val = FakeAST(Int, "-1"));
 262         Text_t index = compile_arguments(env, ast, arg_spec, call->args);
 263         return Texts("List$pop(", self, ", ", index, ", ", compile_type(item_t), ", _, ",
 264                      promote_to_optional(item_t, Text("_")), ", ", compile_none(item_t), ")");
 265     } else if (streq(call->name, "counts")) {
 266         self = compile_to_pointer_depth(env, call->self, 0, false);
 267         (void)compile_arguments(env, ast, NULL, call->args);
 268         return Texts("List$counts(", self, ", ", compile_type_info(self_value_t), ")");
 269     } else {
 270         code_err(ast, "There is no '", call->name, "' method for lists");
 271     }
 272 }