zahl

Log | Files | Refs | README

compile.zig (17923B)

      1 const std = @import("std");
      2 const v = @import("value.zig");
      3 const c = @import("chunk.zig");
      4 const core = @import("core.zig");
      5 
      6 const complog = std.log.scoped(.compile);
      7 
      8 const Storage = union(enum) { local: u32, value: *v.Value };
      9 
     10 const CompileError = error{ InvalidNumberOfArguments, InvalidArgType, UnbalancedBindings, Undefined, OutOfMemory, NotEnoughArguments };
     11 
     12 pub const Compiler = struct {
     13     const Self = @This();
     14 
     15     const CompileState = struct {
     16         return_this: bool,
     17     };
     18 
     19     all: std.mem.Allocator,
     20     val: *v.Value,
     21     func: v.Function,
     22 
     23     // Variable management (+ constant folding)
     24     sym_map: std.StringHashMap(Storage),
     25     scope_depth: u32,
     26 
     27     enclosing: ?*const Compiler = null,
     28 
     29     pub fn init(all: std.mem.Allocator, val: *v.Value) !Self {
     30         return Self{
     31             .all = all,
     32             .val = val.ref(),
     33             .func = v.Function.init(all),
     34             .sym_map = std.StringHashMap(Storage).init(all),
     35             .scope_depth = 0,
     36         };
     37     }
     38 
     39     fn getChunk(self: *Self) *c.Chunk {
     40         return &self.func.code;
     41     }
     42 
     43     pub fn deinit(self: *Self) void {
     44         self.val.unref();
     45         self.sym_map.deinit();
     46     }
     47 
     48     fn isConstant(self: *Self, val: *v.Value) ?*v.Value {
     49         if (val.isA(.number) or val.isA(.nil)) {
     50             return val;
     51         }
     52 
     53         switch (val.val) {
     54             .symbol => |sym| {
     55                 if (self.sym_map.get(sym)) |store| {
     56                     switch (store) {
     57                         .value => |cval| return cval,
     58                         else => {},
     59                     }
     60                 }
     61             },
     62             else => {},
     63         }
     64         return null;
     65     }
     66 
     67     fn compileIntrinsic(self: *Self, index: core.mapping) !void {
     68         const val = core.getIntrinsic(index);
     69         const cst = try self.getChunk().addConstant(try v.Value.newNative(self.all, val));
     70         try self.getChunk().write(.{ .constant = cst });
     71         try self.getChunk().write(.{ .call = val.arity });
     72     }
     73 
     74     // "macro" that allows to perform pattern mathing
     75     // this is nice to generate intrinsics for certain patterns
     76     fn checkMatch(comptime desc: anytype, val: *v.Value) bool {
     77         const rootT = @TypeOf(desc);
     78         switch (rootT) {
     79             v.Special => {
     80                 return val.isA(.special) and val.val.special == desc;
     81             },
     82             v.Value.Tag => {
     83                 return val.isA(desc);
     84             },
     85             else => {},
     86         }
     87 
     88         switch (@typeInfo(rootT)) {
     89             .Struct => |s| {
     90                 if (!val.isA(.list)) {
     91                     return false;
     92                 }
     93 
     94                 const lst = val.val.list;
     95 
     96                 inline for (s.fields, 0..) |field, idx| {
     97                     if (!checkMatch(@field(desc, field.name), lst[idx])) {
     98                         return false;
     99                     }
    100                 }
    101 
    102                 return true;
    103             },
    104             .ComptimeInt => {
    105                 if (!val.isA(.number)) {
    106                     return false;
    107                 }
    108 
    109                 const llen: usize = comptime std.math.big.int.calcLimbLen(desc);
    110                 var limbbuf: [llen]std.math.big.Limb = undefined;
    111                 var mut = std.math.big.int.Mutable.init(&limbbuf, desc).toConst();
    112 
    113                 return mut.eql(val.val.number.toConst());
    114             },
    115             .EnumLiteral => {
    116                 if (desc == .any) {
    117                     return true;
    118                 }
    119             },
    120             else => @compileError("Uninmplemented"),
    121         }
    122     }
    123 
    124     fn compileInner(self: *Self, val: *v.Value, astate: CompileState) CompileError!void {
    125         var state = astate;
    126 
    127         // (= (% val 2) 0) => (even? val)
    128         if (Compiler.checkMatch(.{ v.Special.@"=", .{ v.Special.@"%", .any, 2 }, 0 }, val)) {
    129             try self.compileInner(val.val.list[1].val.list[1], .{ .return_this = false });
    130             try self.compileIntrinsic(.isEven);
    131         // (= (% val 2) 1) => (odd? val)
    132         } else if (Compiler.checkMatch(.{ v.Special.@"=", .{ v.Special.@"%", .any, 2 }, 1 }, val)) {
    133             try self.compileInner(val.val.list[1].val.list[1], .{ .return_this = false });
    134             try self.compileIntrinsic(.isOdd);
    135         // (+ (* v1 v2) v3) => (fma v1 v2 v3)
    136         } else if (Compiler.checkMatch(.{ v.Special.@"+", .{ v.Special.@"*", .any, .any }, .any }, val)) {
    137             try self.compileInner(val.val.list[1].val.list[1], .{ .return_this = false });
    138             try self.compileInner(val.val.list[1].val.list[2], .{ .return_this = false });
    139             try self.compileInner(val.val.list[2], .{ .return_this = false });
    140             try self.compileIntrinsic(.fma);
    141         } else switch (val.val) {
    142             inline .function, .native => |_| @panic("Unreachable"),
    143             .symbol => |sym| {
    144                 if (self.sym_map.get(sym)) |store| {
    145                     switch (store) {
    146                         .local => |index| {
    147                             try self.getChunk().write(.{ .local = index });
    148                         },
    149 
    150                         // This variant takes care of constant folding
    151                         // actual constant folding is done when generating the symbol
    152                         .value => |cst| {
    153                             const cval = try self.getChunk().addConstant(cst.ref());
    154                             try self.getChunk().write(.{ .constant = cval });
    155                         },
    156                     }
    157                 } else {
    158                     // Late binding of global variables
    159                     const symval = try self.getChunk().addConstant(val.ref());
    160                     try self.getChunk().write(.{ .get_global = symval });
    161                 }
    162             },
    163             .special => @panic("Cannot compile special"),
    164             .list => |lst| {
    165                 if (lst[0].isA(.symbol)) {
    166                     // First, push the arguments one by one
    167                     for (lst[1..]) |param| {
    168                         try self.compileInner(param, .{ .return_this = false });
    169                     }
    170 
    171                     // Now either TCO or call
    172                     if (state.return_this and std.mem.eql(u8, lst[0].val.symbol, self.func.name)) {
    173                         if (lst.len - 1 != self.func.arity) {
    174                             return CompileError.NotEnoughArguments;
    175                         }
    176                         try self.getChunk().write(.{ .popscope = .{ .offset = self.func.arity, .scope = self.func.arity } });
    177                         try self.getChunk().write(.{ .jump = 0 });
    178                         state.return_this = false;
    179                     } else {
    180                         const symc = try self.getChunk().addConstant(lst[0].ref());
    181                         try self.getChunk().write(.{ .get_global = symc });
    182                         try self.getChunk().write(.{ .call = lst.len - 1 });
    183                     }
    184                 } else {
    185                     state = try self.compileSpecial(lst[0].val.special, lst, state);
    186                 }
    187             },
    188             .number, .nil, .true, .false => {
    189                 const cst = try self.getChunk().addConstant(val.ref());
    190                 try self.getChunk().write(.{ .constant = cst });
    191             },
    192         }
    193 
    194         if (state.return_this) {
    195             complog.debug("Generate return for {}, offset={}", .{val.formatter(), self.getChunk().nextPc()});
    196             try self.getChunk().write(.@"return");
    197         }
    198     }
    199 
    200     fn compileSpecial(self: *Self, name: v.Special, lst: []*v.Value, state: CompileState) !CompileState {
    201         switch (name) {
    202             inline .@"+", .@"*" => |tag| {
    203                 try self.compileInner(lst[1], .{ .return_this = false });
    204                 for (lst[2..]) |inner| {
    205                     try self.compileInner(inner, .{ .return_this = false });
    206                     try self.getChunk().write(if (tag == .@"+") .add else .multiply);
    207                 }
    208             },
    209             .@"-" => {
    210                 if (lst.len == 2) {
    211                     try self.compileInner(lst[1], .{ .return_this = false });
    212                     try self.getChunk().write(.negate);
    213                 } else {
    214                     try self.compileInner(lst[2], .{ .return_this = false });
    215                     try self.compileInner(lst[1], .{ .return_this = false });
    216                     try self.getChunk().write(.substract);
    217                 }
    218             },
    219 
    220             inline .@"/", .@"%" => |tag| {
    221                 try self.compileInner(lst[2], .{ .return_this = false });
    222                 try self.compileInner(lst[1], .{ .return_this = false });
    223                 try self.getChunk().write(.div);
    224                 try self.getChunk().write(switch (tag) {
    225                     .@"/" => .pop,
    226                     .@"%" => .{
    227                         .popscope = .{ .offset = 1, .scope = 1 },
    228                     },
    229                     else => @compileError("Unreachable"),
    230                 });
    231             },
    232 
    233             inline .@"=", .@"<", .@"^" => |val| {
    234                 try self.compileInner(lst[2], .{ .return_this = false });
    235                 try self.compileInner(lst[1], .{ .return_this = false });
    236                 try self.getChunk().write(switch (val) {
    237                     .@"^" => .pow,
    238                     .@"=" => .{ .compare = .eq },
    239                     .@"<" => .{ .compare = .lt },
    240                     else => @compileError("unreachable"),
    241                 });
    242             },
    243             // (let* (bindings...) expr)
    244             .@"let*" => {
    245                 if (lst.len != 3) {
    246                     return CompileError.InvalidNumberOfArguments;
    247                 }
    248                 if (!lst[1].isA(.list)) {
    249                     return CompileError.InvalidArgType;
    250                 }
    251 
    252                 const blist = lst[1].val.list;
    253                 if (blist.len % 2 != 0) {
    254                     return CompileError.UnbalancedBindings;
    255                 }
    256 
    257                 for (0..blist.len / 2) |idx| {
    258                     const sym = blist[2 * idx];
    259                     const sval = blist[2 * idx + 1];
    260 
    261                     if (!sym.isA(.symbol)) {
    262                         return CompileError.InvalidArgType;
    263                     }
    264 
    265                     // Perform constant folding !!
    266                     const storage: Storage = if (self.isConstant(sval)) |cval|
    267                         .{ .value = cval }
    268                     else blk: {
    269                         try self.compileInner(sval, .{ .return_this = false });
    270                         complog.debug("{s} is at depth {}", .{ sym.val.symbol, self.scope_depth });
    271                         const loc = .{ .local = self.scope_depth };
    272                         self.scope_depth += 1;
    273                         break :blk loc;
    274                     };
    275 
    276                     try self.sym_map.put(sym.val.symbol, storage);
    277                 }
    278 
    279                 // FIXME: TCO for let
    280                 try self.compileInner(lst[2], .{ .return_this = false });
    281 
    282                 // Now, remove the bindings of the variables
    283                 var to_pop: u16 = 0;
    284                 for (0..blist.len / 2) |idx| {
    285                     const got = self.sym_map.fetchRemove(blist[2 * idx].val.symbol).?;
    286                     switch (got.value) {
    287                         .local => {
    288                             to_pop += 1;
    289                             self.scope_depth -= 1;
    290                         },
    291                         .value => {},
    292                     }
    293                 }
    294                 if (to_pop != 0) {
    295                     try self.getChunk().write(.{ .popscope = .{ .scope = to_pop, .offset = 1 } });
    296                 }
    297             },
    298 
    299             // (if cond then else)
    300             .@"if" => {
    301                 if (lst.len != 4) {
    302                     return CompileError.InvalidNumberOfArguments;
    303                 }
    304 
    305                 // Generate cond
    306                 try self.compileInner(lst[1], .{ .return_this = false });
    307 
    308                 // If falsy then jump to else
    309                 try self.getChunk().write(.{ .jumpfalse = undefined });
    310                 const jmpthen = self.getChunk().lastInstrRef();
    311 
    312                 try self.compileInner(lst[2], state);
    313 
    314                 var jmpelse: usize = undefined;
    315                 if (!state.return_this) {
    316                     try self.getChunk().write(.{ .jump = undefined });
    317                     jmpelse = self.getChunk().lastInstrRef();
    318                 }
    319 
    320                 self.getChunk().instrs.items[jmpthen] = .{ .jumpfalse = self.getChunk().nextPc() };
    321                 complog.debug("Backpatched jumpfalse: {}", .{jmpthen});
    322 
    323                 try self.compileInner(lst[3], state);
    324                 if (!state.return_this) {
    325                     self.getChunk().instrs.items[jmpelse] = .{ .jump = self.getChunk().nextPc() };
    326                     complog.debug("Backpatched jump: {}", .{jmpelse});
    327                 }
    328 
    329                 // Either it was false, or we generated the returns in both branches
    330                 return .{ .return_this = false };
    331             },
    332 
    333             // (defn! name (args...) value)
    334             .@"defn!" => {
    335                 if (lst.len != 4) {
    336                     return CompileError.InvalidNumberOfArguments;
    337                 }
    338 
    339                 if (!lst[1].isA(.symbol)) {
    340                     return CompileError.InvalidArgType;
    341                 }
    342 
    343                 if (!lst[2].isA(.list)) {
    344                     return CompileError.InvalidArgType;
    345                 }
    346 
    347                 const args = lst[2].val.list;
    348 
    349                 for (args) |arg| {
    350                     if (!arg.isA(.symbol)) {
    351                         return CompileError.InvalidArgType;
    352                     }
    353                 }
    354 
    355                 const arity = args.len;
    356 
    357                 var inner = try Compiler.init(self.all, lst[3]);
    358                 defer inner.deinit();
    359 
    360                 inner.enclosing = self;
    361                 inner.func.name = lst[1].val.symbol;
    362                 inner.func.arity = @intCast(arity);
    363 
    364                 // Declare the parameters
    365                 for (args) |arg| {
    366                     const loc: Storage = .{ .local = inner.scope_depth };
    367                     inner.scope_depth += 1;
    368                     try inner.sym_map.put(arg.val.symbol, loc);
    369                 }
    370 
    371                 // Now finish compilation
    372                 const res = try inner.compile();
    373                 const valres = try v.Value.newFunction(self.all, res);
    374 
    375                 const vindex = try self.getChunk().addConstant(valres);
    376                 try self.getChunk().write(.{ .constant = vindex });
    377 
    378                 const sym = try self.getChunk().addConstant(lst[1].ref());
    379 
    380                 try self.getChunk().write(.{ .define_global = sym });
    381             },
    382 
    383             // (print expr)
    384             .@"print!" => {
    385                 try self.compileInner(lst[1], .{ .return_this = false });
    386                 try self.getChunk().write(.print);
    387             },
    388 
    389             // (do expr...)
    390             .do => if (lst.len > 1) {
    391                 for (lst[1 .. lst.len - 1]) |ival| {
    392                     try self.compileInner(ival, .{ .return_this = false });
    393                     try self.getChunk().write(.pop);
    394                 }
    395                 try self.compileInner(lst[lst.len - 1], state);
    396 
    397                 return .{ .return_this = false };
    398             },
    399 
    400             .cons => {
    401                 try self.compileInner(lst[2], .{ .return_this = false });
    402                 try self.compileInner(lst[1], .{ .return_this = false });
    403                 try self.getChunk().write(.cons);
    404             },
    405 
    406             .list => {
    407                 var newarr = try self.all.alloc(*v.Value, lst.len - 1);
    408 
    409                 for (lst[1..], 0..) |oval, idx| {
    410                     newarr[idx] = oval.ref();
    411                 }
    412 
    413                 errdefer {
    414                     for (newarr) |nval| {
    415                         nval.unref();
    416                     }
    417                     self.all.free(newarr);
    418                 }
    419 
    420                 const val = try self.getChunk().addConstant(try v.Value.newList(self.all, newarr));
    421                 try self.getChunk().write(.{ .constant = val });
    422             },
    423 
    424             inline .fst, .rest => |tag| {
    425                 try self.compileInner(lst[1], .{ .return_this = false });
    426                 try self.getChunk().write(.uncons);
    427                 try self.getChunk().write(switch (tag) {
    428                     .fst => .{ .popscope = .{ .offset = 1, .scope = 1 } },
    429                     .rest => .pop,
    430                     else => @compileError("unreachable"),
    431                 });
    432             },
    433         }
    434         return state;
    435     }
    436 
    437     pub fn compile(self: *Self) CompileError!v.Function {
    438         try self.compileInner(self.val, .{ .return_this = true });
    439 
    440         if (std.log.logEnabled(.debug, .compile)) {
    441             complog.debug("Compiled version of {}", .{self.val.formatter()});
    442             self.func.code.disassemble();
    443         }
    444 
    445         return self.func;
    446     }
    447 };
    448 
    449 test "Simple match" {
    450     const scan = @import("scan.zig");
    451 
    452     try v.init(std.testing.allocator);
    453     defer v.deinit();
    454 
    455     var offset: ?usize = null;
    456     var scanner = try scan.Reader.init("(% 2 3)", std.testing.allocator, &offset);
    457 
    458     var val = try scanner.readValue(&offset);
    459     defer val.unref();
    460 
    461     try std.testing.expect(Compiler.checkMatch(.{
    462         v.Special.@"%",
    463         2,
    464         3,
    465     }, val));
    466 }
    467 
    468 test "Nested match" {
    469     const scan = @import("scan.zig");
    470     const s = @import("symintern.zig");
    471 
    472     try v.init(std.testing.allocator);
    473     defer v.deinit();
    474 
    475     s.init(std.testing.allocator);
    476     defer s.deinit();
    477 
    478     var offset: ?usize = null;
    479     var scanner = try scan.Reader.init("(= (% val 2) 0)", std.testing.allocator, &offset);
    480 
    481     var val = try scanner.readValue(&offset);
    482     defer val.unref();
    483 
    484     try std.testing.expect(Compiler.checkMatch(.{
    485         v.Special.@"=",
    486         .{ v.Special.@"%", .any, 2 },
    487         0,
    488     }, val));
    489 }