stdlib/compiler/parser/dict.ajla

   1 {*
   2  * Copyright (C) 2024 Mikulas Patocka
   3  *
   4  * This file is part of Ajla.
   5  *
   6  * Ajla is free software: you can redistribute it and/or modify it under the
   7  * terms of the GNU General Public License as published by the Free Software
   8  * Foundation, either version 3 of the License, or (at your option) any later
   9  * version.
  10  *
  11  * Ajla is distributed in the hope that it will be useful, but WITHOUT ANY
  12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  13  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along with
  16  * Ajla. If not, see <https://www.gnu.org/licenses/>.
  17  *}
  18
  19 private unit compiler.parser.dict;
  20
  21 uses io;
  22
  23 uses compiler.parser.istring;
  24 uses compiler.parser.token;
  25 uses pcode;
  26
  27 fn unimplemented(m : bytes) : unit_type;
  28
  29 const T_NoLocalType : int := T_InvalidType;
  30
  31 record variable_dictionary [
  32         dict : list(int);
  33         impl : list(int);
  34         break_label : int;
  35         continue_label : int;
  36         gvn_backup : list(int);
  37         next : maybe(variable_dictionary);
  38         parent : maybe(variable_dictionary);
  39 ]
  40
  41 record local_variable [
  42         type_idx : int;
  43         defined_at : int;
  44         mut : bool;
  45         local_type : int;
  46         name : istring;
  47 ]
  48
  49 const defined_argument : int := 0;
  50 const defined_multiple : int := -1;
  51
  52 record instruction [
  53         opcode : pcode_t;
  54         args : list(pcode_t);
  55 ]
  56
  57 record local_type [
  58         mode : pcode_t;
  59         args : list(pcode_t);
  60 ]
  61
  62 record module_unique_id [
  63         path_index : int;
  64         unit_string : istring;
  65         program : bool;
  66 ]
  67
  68 record function_unique_id [
  69         path_index : int;
  70         unit_string : istring;
  71         program : bool;
  72         function_index : list(int);
  73 ]
  74
  75 implicit fn instance_eq_function_unique_id~inline : class_eq(function_unique_id);
  76
  77 type function_dictionary;
  78
  79 option op_option [
  80         function;
  81         prefix_op;
  82         postfix_op;
  83         infix_op;
  84 ]
  85
  86 const op_name : bytes := "{";
  87 const op_prefix_name : bytes := "}";
  88
  89 record record_entry [
  90         type_idx : int;
  91         cnst : bool;
  92         accessing_other : bool;
  93 ]
  94
  95 record record_definition [
  96         is_option : bool;
  97         is_flat_option : bool;
  98         entries : list(record_entry);
  99         dict : list(int);
 100 ]
 101
 102 type function_definition;
 103
 104 record function_context [
 105         n_arguments : int;
 106         n_return_values : int;
 107         variables : list(local_variable);
 108         instructions : list(instruction);
 109
 110         lambdas : list(function_definition);
 111
 112         n_returns : int;
 113
 114         n_labels : int;
 115         defined_labels : list(bool);
 116         used_labels : list(int);
 117         list_of_used_labels : list(istring);
 118
 119         incomplete : bool;
 120         inferred_return : bool;
 121         name : istring;
 122
 123         op_mode : op_option;
 124         op_priority : int;
 125
 126         record_def : maybe(record_definition);
 127
 128         local_types : list(local_type);
 129         local_types_map : list(int);
 130
 131         dict : function_dictionary;
 132         id : function_unique_id;
 133
 134         parent_function : maybe(function_context);
 135
 136         gvn : list(int);
 137         gvn_seq : int;
 138
 139         inferred_base : int;
 140 ]
 141
 142 record function_definition [
 143         signature : function_context;
 144         body : maybe(function_context);
 145         vd : variable_dictionary;
 146         call_mode : int;
 147         op_bypass : int;
 148         op_bypass_reverse : bool;
 149         typ : int;
 150         private_flag : bool;
 151         pcode : list(pcode_t);
 152 ]
 153
 154 type macro := tokens;
 155
 156 record function_dictionary [
 157         defs : list(function_definition);
 158         dict : list(int);
 159         macros : list(macro);
 160         id : module_unique_id;
 161         impl : list(int);
 162         conv : list(int);
 163         name_prefix : bytes;
 164         priv : bool;
 165         modules : list(function_dictionary);
 166         modules_map : list(int);
 167 ]
 168
 169 fn new_variable_dictionary(parent : maybe(variable_dictionary)) : variable_dictionary;
 170 fn new_variable_dictionary_chained(ctx : function_context, v : variable_dictionary) : variable_dictionary;
 171 fn free_variable_dictionary_chained(ctx : function_context, v : variable_dictionary) : function_context;
 172 fn new_variable(ctx : function_context, t def_at : int, mut : bool) : (function_context, local_variable);
 173 fn set_variable_type(ctx : function_context, idx typ : int) : function_context;
 174 fn add_variable(ctx : function_context, vd : variable_dictionary, name : istring, idx : int, impl : bool, t : tokens) : (function_context, variable_dictionary);
 175 fn search_variable_dictionary(vd : variable_dictionary, name : istring) : int;
 176 fn search_break(vd : variable_dictionary) : int;
 177 fn search_continue(vd : variable_dictionary) : int;
 178 fn get_implicit_variables(vd : variable_dictionary) : list(int);
 179
 180 fn new_function_dictionary(path_index : int, unit_string : istring, program : bool) : function_dictionary;
 181 fn new_function_context(dict : function_dictionary, parent_function : maybe(function_context), n_arguments n_return_values : int, name : istring) : function_context;
 182 fn function_context_is_privileged(ctx : function_context) : bool;
 183 fn function_context_clear_temp_values(ctx : function_context) : function_context;
 184 fn add_function(dict : function_dictionary, name : istring, ctx : function_context, vd : variable_dictionary, call_mode : int, op_bypass : int, op_bypass_reverse : bool, private_flag implicit_flag conversion_flag : bool) : (function_dictionary, function_definition);
 185 fn add_lambda(ctx ctx_head ctx_body : function_context, call_mode : int) : (function_context, function_definition);
 186 fn search_function_dictionary(dict : function_dictionary, name : istring) : function_definition;
 187 fn search_function(ctx : function_context, name : istring, t : tokens) : function_definition;
 188 fn search_function_from_id(ctx : function_context, id : function_unique_id) : function_definition;
 189 fn get_implicits(ctx : function_context, conv : bool) : list(function_definition);
 190 fn new_record_definition(is_option : bool) : record_definition;
 191
 192 fn encode_module_id~inline(id : module_unique_id) : int;
 193
 194 fn dump_function_context(ctx : function_context) : unit_type;
 195
 196 implementation
 197
 198 uses exception;
 199
 200 fn function_unique_id_equal(x1 x2 : function_unique_id) : bool
 201 [
 202         return  x1.path_index = x2.path_index and
 203                 x1.unit_string = x2.unit_string and
 204                 x1.program = x2.program and
 205                 x1.function_index = x2.function_index;
 206 ]
 207
 208 implicit fn instance_eq_function_unique_id~inline : class_eq(function_unique_id) :=
 209         class_eq(function_unique_id).[
 210                 equal : function_unique_id_equal,
 211         ];
 212
 213 fn unimplemented(m : bytes) : unit_type
 214 [
 215         m := "Unimplemented: " + m;
 216         return internal(m);
 217 ]
 218
 219 fn new_variable_dictionary(parent : maybe(variable_dictionary)) : variable_dictionary
 220 [
 221         return variable_dictionary.[
 222                 dict : infinite_uninitialized(int),
 223                 impl : empty(int),
 224                 break_label : -1,
 225                 continue_label : -1,
 226                 gvn_backup : exception_make(list(int), ec_sync, error_record_field_not_initialized, 0, false),
 227                 next : maybe(variable_dictionary).n,
 228                 parent : parent,
 229         ];
 230 ]
 231
 232 fn new_variable_dictionary_chained(ctx : function_context, v : variable_dictionary) : variable_dictionary
 233 [
 234         var vd := new_variable_dictionary(maybe(variable_dictionary).n);
 235         vd.next.j := v;
 236         vd.gvn_backup := ctx.gvn;
 237         return vd;
 238 ]
 239
 240 fn free_variable_dictionary_chained(ctx : function_context, v : variable_dictionary) : function_context
 241 [
 242         ctx.gvn := v.gvn_backup;
 243         return ctx;
 244 ]
 245
 246 fn new_variable(ctx : function_context, t def_at : int, mut : bool) : (function_context, local_variable)
 247 [
 248         return ctx, local_variable.[
 249                 type_idx : t,
 250                 defined_at : def_at,
 251                 mut : mut,
 252                 local_type : T_NoLocalType,
 253                 name : 0,
 254         ];
 255 ]
 256
 257 fn set_variable_type(ctx : function_context, idx typ : int) : function_context
 258 [
 259         ctx.variables[idx].type_idx := typ;
 260         return ctx;
 261 ]
 262
 263 fn add_variable(ctx : function_context, vd : variable_dictionary, name : istring, idx : int, impl : bool, t : tokens) : (function_context, variable_dictionary)
 264 [
 265         if name <> 0 then [
 266                 var existing := vd.dict[name];
 267                 if not is_uninitialized(existing) then [
 268                         abort compiler_error("Variable " + i_decode(name) + " already exists", t);
 269                 ]
 270                 vd.dict[name] := idx;
 271                 ctx.variables[idx].name := name;
 272         ]
 273         if impl then
 274                 vd.impl +<= idx;
 275         return ctx, vd;
 276 ]
 277
 278 fn search_variable_dictionary(vd : variable_dictionary, name : istring) : int
 279 [
 280 again:
 281         var v := vd.dict[name];
 282         if not is_uninitialized(v) then
 283                 return v;
 284         if vd.next is j then [
 285                 vd := vd.next.j;
 286                 goto again;
 287         ]
 288 again2:
 289         if vd.parent is j then [
 290                 vd := vd.parent.j;
 291 again3:
 292                 var v := vd.dict[name];
 293                 if not is_uninitialized(v) then
 294                         return exception_make_str(int, ec_sync, error_user2, 0, false, i_decode(name));
 295                 if vd.next is j then [
 296                         vd := vd.next.j;
 297                         goto again3;
 298                 ]
 299                 goto again2;
 300         ]
 301         return -1;
 302 ]
 303
 304 fn search_break(vd : variable_dictionary) : int
 305 [
 306 lbl:
 307         if vd.break_label >= 0 then
 308                 return vd.break_label;
 309         if vd.next is j then [
 310                 vd := vd.next.j;
 311                 goto lbl;
 312         ]
 313         return -1;
 314 ]
 315
 316 fn search_continue(vd : variable_dictionary) : int
 317 [
 318 lbl:
 319         if vd.continue_label >= 0 then
 320                 return vd.continue_label;
 321         if vd.next is j then [
 322                 vd := vd.next.j;
 323                 goto lbl;
 324         ]
 325         return -1;
 326 ]
 327
 328 fn get_implicit_variables(vd : variable_dictionary) : list(int)
 329 [
 330         var i := len(vd.impl) - 1;
 331         var lst := empty(int);
 332         while i >= 0 do [
 333                 lst +<= vd.impl[i];
 334                 i -= 1;
 335         ]
 336         if vd.next is j then
 337                 lst += get_implicit_variables(vd.next.j);
 338         return lst;
 339 ]
 340
 341 fn new_function_dictionary(path_index : int, unit_string : istring, program : bool) : function_dictionary
 342 [
 343         return function_dictionary.[
 344                 defs : empty(function_definition),
 345                 dict : infinite_uninitialized(int),
 346                 macros : infinite_uninitialized(macro),
 347                 id : module_unique_id.[
 348                         path_index : path_index,
 349                         unit_string : unit_string,
 350                         program : program,
 351                 ],
 352                 impl : empty(int),
 353                 conv : empty(int),
 354                 name_prefix : exception_make(bytes, ec_sync, error_record_field_not_initialized, 0, false),
 355                 priv : false,
 356                 modules : empty(function_dictionary),
 357                 modules_map : infinite_uninitialized(int),
 358         ];
 359 ]
 360
 361 fn new_function_context(dict : function_dictionary, parent_function : maybe(function_context), n_arguments n_return_values : int, name : istring) : function_context
 362 [
 363         var function_index : list(int);
 364         if parent_function is j then
 365                 function_index := parent_function.j.id.function_index +< len(parent_function.j.lambdas);
 366         else
 367                 function_index := [ len(dict.defs) ];
 368         var id := function_unique_id.[
 369                 path_index : dict.id.path_index,
 370                 unit_string : dict.id.unit_string,
 371                 program : dict.id.program,
 372                 function_index : function_index,
 373         ];
 374
 375         var nv := exception_make(local_variable, ec_sync, error_record_field_not_initialized, 0, false);
 376         var ctx := function_context.[
 377                 n_arguments : n_arguments,
 378                 n_return_values : n_return_values,
 379                 variables : fill(nv, n_arguments + n_return_values),
 380                 instructions : empty(instruction),
 381
 382                 lambdas : empty(function_definition),
 383
 384                 n_returns : 0,
 385
 386                 n_labels : 0,
 387                 defined_labels : infinite(false),
 388                 used_labels : infinite_uninitialized(int),
 389                 list_of_used_labels : empty(istring),
 390
 391                 incomplete : true,
 392                 inferred_return : false,
 393                 name : name,
 394
 395                 op_mode : exception_make(op_option, ec_sync, error_record_field_not_initialized, 0, false),
 396                 op_priority : exception_make(int, ec_sync, error_record_field_not_initialized, 0, false),
 397
 398                 record_def : maybe(record_definition).n,
 399
 400                 local_types : empty(local_type),
 401                 local_types_map : infinite_uninitialized(int),
 402
 403                 dict : dict,
 404                 id : id,
 405
 406                 parent_function : parent_function,
 407
 408                 gvn : infinite(-1),
 409                 gvn_seq : 0,
 410
 411                 inferred_base : T_InferredType,
 412         ];
 413         return ctx;
 414 ]
 415
 416 fn function_context_is_privileged(ctx : function_context) : bool
 417 [
 418         return is_privileged or ctx.id.path_index = 0;
 419 ]
 420
 421 fn function_context_clear_temp_values(ctx : function_context) : function_context
 422 [
 423         ctx.dict := exception_make(function_dictionary, ec_sync, error_record_field_not_initialized, 0, false);
 424         return ctx;
 425 ]
 426
 427 fn add_function(dict : function_dictionary, name : istring, ctx : function_context, vd : variable_dictionary, call_mode : int, op_bypass : int, op_bypass_reverse : bool, private_flag implicit_flag conversion_flag : bool) : (function_dictionary, function_definition)
 428 [
 429         ctx := function_context_clear_temp_values(ctx);
 430
 431         var def := function_definition.[
 432                 signature : ctx,
 433                 body : maybe(function_context).n,
 434                 vd : vd,
 435                 call_mode : call_mode,
 436                 op_bypass : op_bypass,
 437                 op_bypass_reverse : op_bypass_reverse,
 438                 typ : exception_make(int, ec_sync, error_record_field_not_initialized, 0, false),
 439                 private_flag : private_flag,
 440                 pcode : exception_make(list(pcode_t), ec_sync, error_record_field_not_initialized, 0, false),
 441         ];
 442
 443         if implicit_flag then
 444                 dict.impl +<= len(dict.defs);
 445
 446         if conversion_flag then
 447                 dict.conv +<= len(dict.defs);
 448
 449         dict.dict[name] := len(dict.defs);
 450         dict.defs +<= def;
 451         return dict, def;
 452 ]
 453
 454 fn add_lambda(ctx ctx_head ctx_body : function_context, call_mode : int) : (function_context, function_definition)
 455 [
 456         ctx_head := function_context_clear_temp_values(ctx_head);
 457         ctx_body := function_context_clear_temp_values(ctx_body);
 458
 459         var def := function_definition.[
 460                 signature : ctx_head,
 461                 body : maybe(function_context).j.(ctx_body),
 462                 call_mode : call_mode,
 463                 op_bypass : -1,
 464                 op_bypass_reverse : false,
 465                 typ : Fn_Function,
 466                 private_flag : true,
 467                 pcode : exception_make(list(pcode_t), ec_sync, error_record_field_not_initialized, 0, false),
 468         ];
 469
 470         ctx.lambdas +<= def;
 471         return ctx, def;
 472 ]
 473
 474 fn search_function_dictionary(dict : function_dictionary, name : istring) : function_definition
 475 [
 476         var fd := dict.defs[dict.dict[name]];
 477         xeval fd;
 478         if fd.signature.inferred_return, fd.body is n then
 479                 return uninitialized(function_definition);
 480         return fd;
 481 ]
 482
 483 fn search_function(ctx : function_context, name : istring, t : tokens) : function_definition
 484 [
 485         var fd := search_function_dictionary(ctx.dict, name);
 486         if not is_uninitialized(fd) then
 487                 return fd;
 488
 489         var dict := ctx.dict;
 490         var found := empty(function_definition);
 491         for i := 0 to len(dict.modules) do [
 492                 fd := search_function_dictionary(dict.modules[i], name);
 493                 if not is_uninitialized(fd) then [
 494                         if fd.private_flag then [
 495                                 if ctx.id.path_index <> fd.signature.id.path_index and not function_context_is_privileged(ctx) then
 496                                         continue;
 497                         ]
 498                         found +<= fd;
 499                 ]
 500         ]
 501
 502         var path_idx := -1;
 503         for i := 0 to len(found) do [
 504                 if found[i].signature.id.path_index > path_idx then
 505                         path_idx := found[i].signature.id.path_index;
 506         ]
 507         var cnt := 0;
 508         for i := 0 to len(found) do [
 509                 if found[i].signature.id.path_index = path_idx then
 510                         cnt += 1;
 511         ]
 512         if cnt > 1 then
 513                 abort compiler_error("Muliple functions named " + i_decode(name), t);
 514         for i := 0 to len(found) do [
 515                 if found[i].signature.id.path_index = path_idx then
 516                         return found[i];
 517         ]
 518
 519         return uninitialized(function_definition);
 520 ]
 521
 522 fn search_function_from_id(ctx : function_context, id : function_unique_id) : function_definition
 523 [
 524         var fd : function_definition;
 525         if ctx.dict.id.path_index = id.path_index, ctx.dict.id.unit_string = id.unit_string, ctx.dict.id.program = id.program then [
 526                 fd := ctx.dict.defs[id.function_index[0]];
 527         ] else [
 528                 var m_id := encode_module_id(module_unique_id.[ path_index : id.path_index, unit_string : id.unit_string, program : id.program ]);
 529
 530                 var m_idx := ctx.dict.modules_map[m_id];
 531                 var m := ctx.dict.modules[m_idx];
 532
 533                 fd := m.defs[id.function_index[0]];
 534         ]
 535         var nested_path := id.function_index[1 .. ];
 536         for p in list_consumer(nested_path) do [
 537                 if fd.body is j then
 538                         fd := fd.body.j.lambdas[p];
 539                 else
 540                         fd := fd.signature.lambdas[p];
 541         ]
 542
 543         return fd;
 544 ]
 545
 546 fn get_implicits(ctx : function_context, conv : bool) : list(function_definition)
 547 [
 548         var this_unit := empty(function_definition);
 549         var max_path_index := ctx.dict.id.path_index;
 550         var all_units : list(list(function_definition)) := fill(empty(function_definition), max_path_index + 1);
 551
 552         var lst : list(int);
 553         if not conv then
 554                 lst := ctx.dict.impl;
 555         else
 556                 lst := ctx.dict.conv;
 557         var i := len(lst) - 1;
 558         while i >= 0 do [
 559                 var idx := lst[i];
 560                 this_unit +<= ctx.dict.defs[idx];
 561                 i -= 1;
 562         ]
 563
 564         var dict := ctx.dict;
 565         for i := 0 to len(dict.modules) do [
 566                 var md := dict.modules[i];
 567                 if md.id.path_index > max_path_index then
 568                         continue;
 569
 570                 if not conv then
 571                         lst := md.impl;
 572                 else
 573                         lst := md.conv;
 574                 var i := len(lst) - 1;
 575                 while i >= 0 do [
 576                         var idx := lst[i];
 577                         all_units[md.id.path_index] +<= md.defs[idx];
 578                         i -= 1;
 579                 ]
 580         ]
 581
 582
 583         var result := this_unit;
 584         i := max_path_index;
 585         while i >= 0 do [
 586                 result += all_units[i];
 587                 i -= 1;
 588         ]
 589
 590         return result;
 591 ]
 592
 593 fn new_record_definition(is_option : bool) : record_definition
 594 [
 595         return record_definition. [
 596                 is_option : is_option,
 597                 is_flat_option : false,
 598                 entries : empty(record_entry),
 599                 dict : infinite_uninitialized(int),
 600         ];
 601 ]
 602
 603
 604 fn encode_module_id~inline(id : module_unique_id) : int
 605 [
 606         if id.path_index <= 7 then
 607                 return id.path_index shl 1 or id.unit_string shl 4;
 608         else
 609                 return 1 or id.path_index shl 1 or id.unit_string shl 32;
 610 ]
 611
 612 fn dump_function_context(ctx : function_context) : unit_type
 613 [
 614         eval debug("--- dumping function: " + i_decode(ctx.name));
 615         for i := 0 to len(ctx.instructions) do [
 616                 var ins := ctx.instructions[i];
 617                 var instr_name := (ntos(i) + " " + pcode_name(ins.opcode) + "                    ")[ .. 20];
 618                 var msg := "instr: " + instr_name + "   ";
 619                 for j := 0 to len(ins.args) do
 620                         msg += " " + ntos(ins.args[j]);
 621                 eval debug(msg);
 622         ]
 623         for i := 0 to len(ctx.variables) do [
 624                 var va := ctx.variables[i];
 625                 var name := "";
 626                 {if va.name <> 0 then
 627                         name := i_decode(va.name);}
 628                 var var_name := (ntos(i) + " " + ntos_base(va.name, 16) + "                    ")[ .. 20];
 629                 var msg := "var: " + var_name + "   ";
 630                 msg += "type_idx: " + ntos(va.type_idx) + ",";
 631                 msg += " defined_at: " + ntos(va.defined_at) + ",";
 632                 msg += " local_type: " + ntos(va.local_type);
 633                 eval debug(msg);
 634         ]
 635         eval debug("---");
 636         return unit_value;
 637 ]