sylt_compiler/
compiler.rs

1use std::cell::RefCell;
2use std::collections::{hash_map::Entry, HashMap};
3use std::path::{Path, PathBuf};
4use std::rc::Rc;
5use sylt_common::error::Error;
6use sylt_common::prog::Prog;
7use sylt_common::{Blob, Block, Op, RustFunction, Type, Value};
8use sylt_parser::{
9    Assignable, AssignableKind, Expression, ExpressionKind, Identifier, Module, Op as ParserOp,
10    Span, Statement, StatementKind, Type as ParserType, TypeKind, VarKind, AST,
11};
12
13type VarSlot = usize;
14
15#[derive(Debug, Clone)]
16struct Variable {
17    name: String,
18    ty: Type,
19    slot: usize,
20    line: usize,
21    kind: VarKind,
22
23    captured: bool,
24    active: bool,
25}
26
27impl Variable {
28    fn new(name: String, kind: VarKind, ty: Type, slot: usize, span: Span) -> Self {
29        Self {
30            name,
31            ty,
32            slot,
33            kind,
34            line: span.line,
35
36            captured: false,
37            active: false,
38        }
39    }
40}
41
42#[derive(Debug, Clone)]
43struct Upvalue {
44    parent: usize,
45    upupvalue: bool,
46
47    name: String,
48    ty: Type,
49    slot: usize,
50    line: usize,
51    kind: VarKind,
52}
53
54enum Lookup {
55    Upvalue(Upvalue),
56    Variable(Variable),
57}
58
59impl Upvalue {
60    fn capture(var: &Variable) -> Self {
61        Self {
62            parent: var.slot,
63            upupvalue: false,
64
65            name: var.name.clone(),
66            ty: var.ty.clone(),
67            slot: 0,
68            line: var.line,
69            kind: var.kind,
70        }
71    }
72
73    fn loft(up: &Upvalue) -> Self {
74        Self {
75            parent: up.slot,
76            upupvalue: true,
77            slot: 0,
78            ..up.clone()
79        }
80    }
81}
82
83#[derive(Debug, Copy, Clone)]
84struct Context {
85    block_slot: BlockID,
86    namespace: NamespaceID,
87    scope: usize,
88    frame: usize,
89}
90
91impl Context {
92    fn from_namespace(namespace: NamespaceID) -> Self {
93        Self {
94            namespace,
95            block_slot: 0,
96            scope: 0,
97            frame: 0,
98        }
99    }
100}
101
102type Namespace = HashMap<String, Name>;
103type ConstantID = usize;
104type NamespaceID = usize;
105type BlobID = usize;
106type BlockID = usize;
107#[derive(Debug, Copy, Clone)]
108enum Name {
109    Global(ConstantID),
110    Blob(BlobID),
111    Namespace(NamespaceID),
112}
113
114#[derive(Debug, Copy, Clone)]
115struct LoopFrame {
116    continue_addr: usize,
117    break_addr: usize,
118    stack_size: usize,
119}
120
121#[derive(Debug)]
122/// Emulates the runtime stackframe.
123/// [variables] and [upvalues] are used like stacks.
124struct Frame {
125    variables: Vec<Variable>,
126    upvalues: Vec<Upvalue>,
127}
128
129impl Frame {
130    fn new(name: &str, span: Span) -> Self {
131        let variables = vec![Variable::new(
132            name.to_string(),
133            VarKind::Const,
134            Type::Void,
135            0,
136            span,
137        )];
138        Self {
139            variables,
140            upvalues: Vec::new(),
141        }
142    }
143}
144
145struct Compiler {
146    blocks: Vec<Block>,
147    namespace_id_to_path: HashMap<NamespaceID, PathBuf>,
148
149    namespaces: Vec<Namespace>,
150    blobs: Vec<Blob>,
151
152    loops: Vec<LoopFrame>,
153    frames: Vec<Frame>,
154    functions: HashMap<String, (usize, RustFunction)>,
155
156    panic: bool,
157    errors: Vec<Error>,
158
159    strings: Vec<String>,
160    constants: Vec<Value>,
161
162    values: HashMap<Value, usize>,
163}
164
165macro_rules! error {
166    ($compiler:expr, $ctx:expr, $span:expr, $( $msg:expr ),+ ) => {
167        if !$compiler.panic {
168            $compiler.panic = true;
169
170            let msg = format!($( $msg ),*).into();
171            let err = Error::CompileError {
172                file: $compiler.file_from_namespace($ctx.namespace).into(),
173                span: $span,
174                message: Some(msg),
175            };
176            $compiler.errors.push(err);
177        }
178    };
179}
180
181impl Compiler {
182    fn new() -> Self {
183        Self {
184            blocks: Vec::new(),
185
186            namespace_id_to_path: HashMap::new(),
187            namespaces: Vec::new(),
188            blobs: Vec::new(),
189
190            loops: Vec::new(),
191            frames: Vec::new(),
192            functions: HashMap::new(),
193
194            panic: false,
195            errors: Vec::new(),
196
197            strings: Vec::new(),
198            constants: Vec::new(),
199
200            values: HashMap::new(),
201        }
202    }
203
204    fn push_frame_and_block(&mut self, ctx: Context, name: &str, span: Span) -> Context {
205        let file_as_path = PathBuf::from(self.file_from_namespace(ctx.namespace));
206
207        let block = Block::new(&name, ctx.namespace, &file_as_path);
208        self.blocks.push(block);
209
210        self.frames.push(Frame::new(name, span));
211        Context {
212            block_slot: self.blocks.len() - 1,
213            frame: self.frames.len() - 1,
214            ..ctx
215        }
216    }
217
218    fn pop_frame(&mut self, ctx: Context) -> Frame {
219        assert_eq!(
220            self.frames.len() - 1,
221            ctx.frame,
222            "Can only pop top stackframe"
223        );
224        self.frames.pop().unwrap()
225    }
226
227    fn file_from_namespace(&self, namespace: usize) -> &Path {
228        self.namespace_id_to_path.get(&namespace).unwrap()
229    }
230
231    fn string(&mut self, string: &str) -> usize {
232        self.strings
233            .iter()
234            .enumerate()
235            .find_map(|(i, x)| if x == string { Some(i) } else { None })
236            .unwrap_or_else(|| {
237                let slot = self.strings.len();
238                self.strings.push(string.into());
239                slot
240            })
241    }
242
243    fn constant(&mut self, value: Value) -> Op {
244        let slot = match self.values.entry(value.clone()) {
245            Entry::Vacant(e) => {
246                let slot = self.constants.len();
247                e.insert(slot);
248                self.constants.push(value);
249                slot
250            }
251            Entry::Occupied(e) => *e.get(),
252        };
253        Op::Constant(slot)
254    }
255
256    fn add_op(&mut self, ctx: Context, span: Span, op: Op) -> usize {
257        self.blocks
258            .get_mut(ctx.block_slot)
259            .expect("Invalid block id")
260            .add(op, span.line)
261    }
262
263    fn patch(&mut self, ctx: Context, ip: usize, op: Op) {
264        self.blocks
265            .get_mut(ctx.block_slot)
266            .expect("Invalid block id")
267            .ops[ip] = op;
268    }
269
270    fn next_ip(&mut self, ctx: Context) -> usize {
271        self.blocks
272            .get_mut(ctx.block_slot)
273            .expect("Invalid block id")
274            .curr()
275    }
276
277    fn pop_until_size(&mut self, ctx: Context, span: Span, target_size: usize) {
278        while target_size < self.frames[ctx.frame].variables.len() {
279            let var = self.frames[ctx.frame].variables.pop().unwrap();
280            if var.captured {
281                self.add_op(ctx, span, Op::PopUpvalue);
282            } else {
283                self.add_op(ctx, span, Op::Pop);
284            }
285        }
286    }
287
288    fn assignable(&mut self, ass: &Assignable, ctx: Context) -> Option<usize> {
289        use AssignableKind::*;
290
291        match &ass.kind {
292            Read(ident) => {
293                return self.read_identifier(&ident.name, ass.span, ctx, ctx.namespace);
294            }
295            Call(f, expr) => {
296                self.assignable(f, ctx);
297                for expr in expr.iter() {
298                    self.expression(expr, ctx);
299                }
300                self.add_op(ctx, ass.span, Op::Call(expr.len()));
301            }
302            ArrowCall(pre, f, expr) => {
303                self.expression(pre, ctx);
304                self.assignable(f, ctx);
305                self.add_op(ctx, ass.span, Op::Swap);
306                for expr in expr.iter() {
307                    self.expression(expr, ctx);
308                }
309                self.add_op(ctx, ass.span, Op::Call(expr.len() + 1));
310            }
311            Access(a, field) => {
312                if let Some(namespace) = self.assignable(a, ctx) {
313                    return self.read_identifier(&field.name, field.span, ctx, namespace);
314                } else {
315                    let slot = self.string(&field.name);
316                    self.add_op(ctx, field.span, Op::GetField(slot));
317                }
318            }
319            Index(a, b) => {
320                self.assignable(a, ctx);
321                if let ExpressionKind::Int(n) = b.kind {
322                    self.add_op(ctx, ass.span, Op::GetConstIndex(n));
323                } else {
324                    self.expression(b, ctx);
325                    self.add_op(ctx, ass.span, Op::GetIndex);
326                }
327            }
328        }
329        None
330    }
331
332    fn un_op(&mut self, a: &Expression, ops: &[Op], span: Span, ctx: Context) {
333        self.expression(&a, ctx);
334        for op in ops {
335            self.add_op(ctx, span, *op);
336        }
337    }
338
339    fn bin_op(&mut self, a: &Expression, b: &Expression, ops: &[Op], span: Span, ctx: Context) {
340        self.expression(&a, ctx);
341        self.expression(&b, ctx);
342        for op in ops {
343            self.add_op(ctx, span, *op);
344        }
345    }
346
347    fn push(&mut self, value: Value, span: Span, ctx: Context) {
348        let value = self.constant(value);
349        self.add_op(ctx, span, value);
350    }
351
352    fn expression(&mut self, expression: &Expression, ctx: Context) {
353        use ExpressionKind::*;
354
355        match &expression.kind {
356            Get(a) => {
357                self.assignable(a, ctx);
358            }
359
360            TypeConstant(ty) => {
361                let resolved_ty = self.resolve_type(ty, ctx);
362                let ty_constant = self.constant(Value::Ty(resolved_ty));
363                self.add_op(ctx, expression.span, ty_constant);
364            }
365
366            Add(a, b) => self.bin_op(a, b, &[Op::Add], expression.span, ctx),
367            Sub(a, b) => self.bin_op(a, b, &[Op::Sub], expression.span, ctx),
368            Mul(a, b) => self.bin_op(a, b, &[Op::Mul], expression.span, ctx),
369            Div(a, b) => self.bin_op(a, b, &[Op::Div], expression.span, ctx),
370
371            Eq(a, b) => self.bin_op(a, b, &[Op::Equal], expression.span, ctx),
372            Neq(a, b) => self.bin_op(a, b, &[Op::Equal, Op::Not], expression.span, ctx),
373            Gt(a, b) => self.bin_op(a, b, &[Op::Greater], expression.span, ctx),
374            Gteq(a, b) => self.bin_op(a, b, &[Op::Less, Op::Not], expression.span, ctx),
375            Lt(a, b) => self.bin_op(a, b, &[Op::Less], expression.span, ctx),
376            Lteq(a, b) => self.bin_op(a, b, &[Op::Greater, Op::Not], expression.span, ctx),
377
378            Is(a, b) => self.bin_op(a, b, &[Op::Is], expression.span, ctx),
379
380            AssertEq(a, b) => self.bin_op(a, b, &[Op::Equal, Op::Assert], expression.span, ctx),
381
382            Neg(a) => self.un_op(a, &[Op::Neg], expression.span, ctx),
383
384            In(a, b) => self.bin_op(a, b, &[Op::Contains], expression.span, ctx),
385
386            And(a, b) => {
387                self.expression(a, ctx);
388
389                self.add_op(ctx, expression.span, Op::Copy(1));
390                let jump = self.add_op(ctx, expression.span, Op::Illegal);
391                self.add_op(ctx, expression.span, Op::Pop);
392
393                self.expression(b, ctx);
394
395                let op = Op::JmpFalse(self.next_ip(ctx));
396                self.patch(ctx, jump, op);
397            }
398            Or(a, b) => {
399                self.expression(a, ctx);
400
401                self.add_op(ctx, expression.span, Op::Copy(1));
402                let skip = self.add_op(ctx, expression.span, Op::Illegal);
403                let jump = self.add_op(ctx, expression.span, Op::Illegal);
404
405                let op = Op::JmpFalse(self.next_ip(ctx));
406                self.patch(ctx, skip, op);
407                self.add_op(ctx, expression.span, Op::Pop);
408
409                self.expression(b, ctx);
410                let op = Op::Jmp(self.next_ip(ctx));
411                self.patch(ctx, jump, op);
412            }
413            Not(a) => self.un_op(a, &[Op::Not], expression.span, ctx),
414
415            Duplicate(a) => self.un_op(a, &[Op::Copy(1)], expression.span, ctx),
416
417            IfExpression {
418                condition,
419                pass,
420                fail,
421            } => {
422                self.expression(condition, ctx);
423
424                let skip = self.add_op(ctx, expression.span, Op::Illegal);
425
426                self.expression(pass, ctx);
427                let out = self.add_op(ctx, expression.span, Op::Illegal);
428                let op = Op::JmpFalse(self.next_ip(ctx));
429                self.patch(ctx, skip, op);
430
431                self.expression(fail, ctx);
432                let op = Op::Jmp(self.next_ip(ctx));
433                self.patch(ctx, out, op);
434
435                self.add_op(ctx, expression.span, Op::Union);
436            }
437
438            IfShort {
439                condition,
440                fail,
441            } => {
442                // Results in 2 values pushed on the stack - since there's a Duplicate in
443                // there!
444                self.expression(condition, ctx);
445
446                let skip = self.add_op(ctx, expression.span, Op::Illegal);
447                let out = self.add_op(ctx, expression.span, Op::Illegal);
448
449                // Only done during the typechecker - mitigates the pop-operation
450                // so the types can be compound.
451                self.add_op(ctx, expression.span, Op::Copy(1));
452
453                let op = Op::JmpFalse(self.next_ip(ctx));
454                self.patch(ctx, skip, op);
455
456                self.add_op(ctx, expression.span, Op::Pop);
457                self.expression(fail, ctx);
458                let op = Op::Jmp(self.next_ip(ctx));
459                self.patch(ctx, out, op);
460
461                self.add_op(ctx, expression.span, Op::Union);
462            }
463
464
465            Function {
466                name,
467                params,
468                ret,
469                body,
470            } => {
471                let file = self.file_from_namespace(ctx.namespace).display();
472                let name = format!("fn {} {}:{}", name, file, expression.span.line);
473
474                // === Frame begin ===
475                let inner_ctx = self.push_frame_and_block(ctx, &name, expression.span);
476                let mut param_types = Vec::new();
477                for (ident, ty) in params.iter() {
478                    param_types.push(self.resolve_type(&ty, inner_ctx));
479                    let param = self.define(&ident.name, VarKind::Const, ident.span);
480                    self.activate(param);
481                }
482                let ret = self.resolve_type(&ret, inner_ctx);
483                let ty = Type::Function(param_types, Box::new(ret));
484                self.blocks[inner_ctx.block_slot].ty = ty.clone();
485
486                self.statement(&body, inner_ctx);
487
488                if !all_paths_return(&body) {
489                    let nil = self.constant(Value::Nil);
490                    self.add_op(inner_ctx, body.span, nil);
491                    self.add_op(inner_ctx, body.span, Op::Return);
492                }
493
494                self.blocks[inner_ctx.block_slot].upvalues = self
495                    .pop_frame(inner_ctx)
496                    .upvalues
497                    .into_iter()
498                    .map(|u| (u.parent, u.upupvalue, u.ty))
499                    .collect();
500                let function = Value::Function(Rc::new(Vec::new()), ty, inner_ctx.block_slot);
501                // === Frame end ===
502
503                let function = self.constant(function);
504                self.add_op(ctx, expression.span, function);
505            }
506
507            Instance { blob, fields } => {
508                self.assignable(blob, ctx);
509                for (name, field) in fields.iter() {
510                    let name = self.constant(Value::Field(name.clone()));
511                    self.add_op(ctx, field.span, name);
512                    self.expression(field, ctx);
513                }
514                self.add_op(ctx, expression.span, Op::Call(fields.len() * 2));
515            }
516
517            Tuple(x) | List(x) | Set(x) | Dict(x) => {
518                for expr in x.iter() {
519                    self.expression(expr, ctx);
520                }
521                self.add_op(
522                    ctx,
523                    expression.span,
524                    match &expression.kind {
525                        Tuple(_) => Op::Tuple(x.len()),
526                        List(_) => Op::List(x.len()),
527                        Set(_) => Op::Set(x.len()),
528                        Dict(_) => Op::Dict(x.len()),
529                        _ => unreachable!(),
530                    },
531                );
532            }
533
534            Float(a) => self.push(Value::Float(*a), expression.span, ctx),
535            Bool(a) => self.push(Value::Bool(*a), expression.span, ctx),
536            Int(a) => self.push(Value::Int(*a), expression.span, ctx),
537            Str(a) => self.push(Value::String(Rc::new(a.clone())), expression.span, ctx),
538            Nil => self.push(Value::Nil, expression.span, ctx),
539        }
540    }
541
542    fn resolve_and_capture(&mut self, name: &str, frame: usize, span: Span) -> Result<Lookup, ()> {
543        // Frame 0 has globals which cannot be captured.
544        if frame == 0 {
545            return Err(());
546        }
547
548        let variables = &self.frames[frame].variables;
549        for var in variables.iter().rev() {
550            if &var.name == name && var.active {
551                return Ok(Lookup::Variable(var.clone()));
552            }
553        }
554
555        let upvalues = &self.frames[frame].upvalues;
556        for up in upvalues.iter().rev() {
557            if &up.name == name {
558                return Ok(Lookup::Upvalue(up.clone()));
559            }
560        }
561
562        let up = match self.resolve_and_capture(name, frame - 1, span) {
563            Ok(Lookup::Upvalue(up)) => Upvalue::loft(&up),
564            Ok(Lookup::Variable(var)) => Upvalue::capture(&var),
565            _ => {
566                return Err(());
567            }
568        };
569        let up = self.upvalue(up, frame);
570        Ok(Lookup::Upvalue(up))
571    }
572
573    fn read_identifier(
574        &mut self,
575        name: &str,
576        span: Span,
577        ctx: Context,
578        namespace: usize,
579    ) -> Option<usize> {
580        match self.resolve_and_capture(name, ctx.frame, span) {
581            Ok(Lookup::Upvalue(up)) => {
582                let op = Op::ReadUpvalue(up.slot);
583                self.add_op(ctx, span, op);
584            }
585
586            Ok(Lookup::Variable(var)) => {
587                let op = Op::ReadLocal(var.slot);
588                self.add_op(ctx, span, op);
589            }
590
591            Err(()) => match self.namespaces[namespace].get(name) {
592                Some(Name::Global(slot)) => {
593                    let op = Op::ReadGlobal(*slot);
594                    self.add_op(ctx, span, op);
595                }
596                Some(Name::Blob(blob)) => {
597                    let op = Op::Constant(*blob);
598                    self.add_op(ctx, span, op);
599                }
600                Some(Name::Namespace(new_namespace)) => return Some(*new_namespace),
601                None => {
602                    if let Some((slot, _)) = self.functions.get(name) {
603                        let slot = *slot;
604                        let op = self.constant(Value::ExternFunction(slot));
605                        self.add_op(ctx, span, op);
606                    } else {
607                        error!(
608                            self,
609                            ctx,
610                            span,
611                            "Cannot read '{}' in '{}'",
612                            name,
613                            self.file_from_namespace(namespace).display()
614                        );
615                    }
616                }
617            },
618        }
619        None
620    }
621
622    fn set_identifier(&mut self, name: &str, span: Span, ctx: Context, namespace: usize) {
623        match self.resolve_and_capture(name, ctx.frame, span) {
624            Ok(Lookup::Upvalue(up)) => {
625                let op = Op::AssignUpvalue(up.slot);
626                self.add_op(ctx, span, op);
627                return;
628            }
629
630            Ok(Lookup::Variable(var)) => {
631                let op = Op::AssignLocal(var.slot);
632                self.add_op(ctx, span, op);
633                return;
634            }
635
636            Err(()) => match self.namespaces[namespace].get(name) {
637                Some(Name::Global(slot)) => {
638                    let var = &self.frames[0].variables[*slot];
639                    if var.kind.immutable() && ctx.frame != 0 {
640                        error!(self, ctx, span, "Cannot mutate constant '{}'", name);
641                    } else {
642                        let op = Op::AssignGlobal(var.slot);
643                        self.add_op(ctx, span, op);
644                    }
645                }
646
647                _ => {
648                    error!(
649                        self,
650                        ctx,
651                        span,
652                        "Cannot assign '{}' in '{}'",
653                        name,
654                        self.file_from_namespace(namespace).display()
655                    );
656                }
657            },
658        }
659    }
660
661    fn resolve_type_namespace(
662        &mut self,
663        assignable: &Assignable,
664        namespace: usize,
665        ctx: Context,
666    ) -> Option<usize> {
667        use AssignableKind::*;
668        match &assignable.kind {
669            Access(inner, ident) => self
670                .resolve_type_namespace(&inner, namespace, ctx)
671                .and_then(|namespace| self.namespaces[namespace].get(&ident.name))
672                .and_then(|o| match o {
673                    Name::Namespace(namespace) => Some(*namespace),
674                    _ => None,
675                })
676                .or_else(|| {
677                    error!(
678                        self,
679                        ctx,
680                        assignable.span,
681                        "While parsing namespace access '{}' is not a namespace",
682                        ident.name
683                    );
684                    None
685                }),
686            Read(ident) => {
687                self
688                .namespaces[namespace].get(&ident.name)
689                .and_then(|o| match o {
690                    Name::Namespace(namespace) => Some(*namespace),
691                    _ => None,
692                })
693                .or_else(|| {
694                    error!(
695                        self,
696                        ctx,
697                        assignable.span,
698                        "While parsing namespace '{}' is not a namespace",
699                        ident.name
700                    );
701                None
702                })
703            }
704            ArrowCall(..) | Call(..) => {
705                error!(self, ctx, assignable.span, "Cannot have calls in types");
706                None
707            }
708            Index(_, _) => {
709                error!(self, ctx, assignable.span, "Cannot have indexing in types");
710                None
711            }
712        }
713    }
714
715    fn resolve_type_ident(
716        &mut self,
717        assignable: &Assignable,
718        namespace: usize,
719        ctx: Context,
720    ) -> Type {
721        use AssignableKind::*;
722        match &assignable.kind {
723            Read(ident) => self.namespaces[namespace]
724                .get(&ident.name)
725                .and_then(|name| match name {
726                    Name::Blob(blob) => Some(Type::Instance(*blob)),
727                    _ => None,
728                })
729                .unwrap_or_else(|| {
730                    error!(
731                        self,
732                        ctx, assignable.span, "While parsing type '{}' is not a blob", ident.name
733                    );
734                    Type::Void
735                }),
736            Access(inner, ident) => self
737                .resolve_type_namespace(&inner, namespace, ctx)
738                .and_then(|namespace| self.namespaces[namespace].get(&ident.name))
739                .and_then(|name| match name {
740                    Name::Blob(blob) => Some(Type::Instance(*blob)),
741                    _ => None,
742                })
743                .unwrap_or_else(|| {
744                    error!(
745                        self,
746                        ctx, assignable.span, "While parsing type '{}' is not a blob", ident.name
747                    );
748                    Type::Void
749                }),
750            ArrowCall(..) | Call(..) => {
751                error!(self, ctx, assignable.span, "Cannot have calls in types");
752                Type::Void
753            }
754            Index(..) => {
755                error!(self, ctx, assignable.span, "Cannot have indexing in types");
756                Type::Void
757            }
758        }
759    }
760
761    fn resolve_type(&mut self, ty: &ParserType, ctx: Context) -> Type {
762        use TypeKind::*;
763        match &ty.kind {
764            Implied => Type::Unknown,
765            Resolved(ty) => ty.clone(),
766            UserDefined(assignable) => self.resolve_type_ident(&assignable, ctx.namespace, ctx),
767            Union(a, b) => match (self.resolve_type(a, ctx), self.resolve_type(b, ctx)) {
768                (Type::Union(_), _) => panic!("Didn't expect union on RHS - check parser"),
769                (a, Type::Union(mut us)) => {
770                    us.insert(a);
771                    Type::Union(us)
772                }
773                (a, b) => Type::Union(vec![a, b].into_iter().collect()),
774            },
775            Fn(params, ret) => {
776                let params = params.iter().map(|t| self.resolve_type(t, ctx)).collect();
777                let ret = Box::new(self.resolve_type(ret, ctx));
778                Type::Function(params, ret)
779            }
780            Tuple(fields) => {
781                Type::Tuple(fields.iter().map(|t| self.resolve_type(t, ctx)).collect())
782            }
783            List(kind) => Type::List(Box::new(self.resolve_type(kind, ctx))),
784            Set(kind) => Type::Set(Box::new(self.resolve_type(kind, ctx))),
785            Dict(key, value) => Type::Dict(
786                Box::new(self.resolve_type(key, ctx)),
787                Box::new(self.resolve_type(value, ctx)),
788            ),
789        }
790    }
791
792    fn define(&mut self, name: &str, kind: VarKind, span: Span) -> VarSlot {
793        let frame = &mut self.frames.last_mut().unwrap().variables;
794        let slot = frame.len();
795        let var = Variable::new(name.to_string(), kind, Type::Unknown, slot, span);
796        frame.push(var);
797        slot
798    }
799
800    fn upvalue(&mut self, mut up: Upvalue, frame: usize) -> Upvalue {
801        let ups = &mut self.frames[frame].upvalues;
802        let slot = ups.len();
803        up.slot = slot;
804        ups.push(up.clone());
805        up
806    }
807
808    fn activate(&mut self, slot: VarSlot) {
809        self.frames.last_mut().unwrap().variables[slot].active = true;
810    }
811
812    fn statement(&mut self, statement: &Statement, ctx: Context) {
813        use StatementKind::*;
814        self.panic = false;
815
816        match &statement.kind {
817            Use { .. } | EmptyStatement => {}
818
819            Blob { name, fields } => {
820                if let Some(Name::Blob(slot)) = self.namespaces[ctx.namespace].get(name) {
821                    let slot = *slot;
822                    self.blobs[slot].fields = fields
823                        .clone()
824                        .into_iter()
825                        .map(|(k, v)| (k, self.resolve_type(&v, ctx)))
826                        .collect();
827                } else {
828                    error!(
829                        self,
830                        ctx,
831                        statement.span,
832                        "No blob with the name '{}' in this namespace (#{})",
833                        name,
834                        ctx.namespace
835                    );
836                }
837            }
838
839            IsCheck { lhs, rhs } => {
840                let lhs = self.resolve_type(lhs, ctx);
841                let rhs = self.resolve_type(rhs, ctx);
842                if let Err(msg) = rhs.fits(&lhs, &self.blobs) {
843                    error!(
844                        self,
845                        ctx, statement.span,
846                        "Is-check failed - {}",
847                        msg
848                    );
849                }
850            }
851
852            Print { value } => {
853                self.expression(value, ctx);
854                self.add_op(ctx, statement.span, Op::Print);
855            }
856
857            #[rustfmt::skip]
858            Definition { ident, kind, ty, value } => {
859                // TODO(ed): Don't use type here - type check the tree first.
860                self.expression(value, ctx);
861
862                if ctx.frame == 0 {
863                    // Global
864                    self.set_identifier(&ident.name, statement.span, ctx, ctx.namespace);
865                } else {
866                    // Local variable
867                    let slot = self.define(&ident.name, *kind, statement.span);
868                    let ty = self.resolve_type(ty, ctx);
869                    let op = if let Op::Constant(ty) = self.constant(Value::Ty(ty)) {
870                        if kind.force() {
871                            Op::Force(ty)
872                        } else {
873                            Op::Define(ty)
874                        }
875                    } else {
876                        error!(self, ctx, statement.span, "Failed to add type declaration");
877                        Op::Illegal
878                    };
879                    self.add_op(ctx, statement.span, op);
880                    self.activate(slot);
881                }
882            }
883
884            #[rustfmt::skip]
885            Assignment { target, value, kind } => {
886                use AssignableKind::*;
887                use ParserOp::*;
888
889                let mutator = |kind| matches!(kind, Add | Sub | Mul | Div);
890
891                let write_mutator_op = |comp: &mut Self, ctx, kind| {
892                    let op = match kind {
893                        Add => Op::Add,
894                        Sub => Op::Sub,
895                        Mul => Op::Mul,
896                        Div => Op::Div,
897                        Nop => {
898                            return;
899                        }
900                    };
901                    comp.add_op(ctx, statement.span, op);
902                };
903
904                match &target.kind {
905                    Read(ident) => {
906                        if mutator(*kind) {
907                            self.read_identifier(&ident.name, statement.span, ctx, ctx.namespace);
908                        }
909                        self.expression(value, ctx);
910
911                        write_mutator_op(self, ctx, *kind);
912
913                        self.set_identifier(&ident.name, statement.span, ctx, ctx.namespace);
914                    }
915                    ArrowCall(..) | Call(..) => {
916                        error!(
917                            self,
918                            ctx, statement.span, "Cannot assign to result from function call"
919                        );
920                    }
921                    Access(a, field) => {
922                        self.assignable(a, ctx);
923                        let slot = self.string(&field.name);
924
925                        if mutator(*kind) {
926                            self.add_op(ctx, statement.span, Op::Copy(1));
927                            self.add_op(ctx, field.span, Op::GetField(slot));
928                        }
929                        self.expression(value, ctx);
930                        write_mutator_op(self, ctx, *kind);
931
932                        self.add_op(ctx, field.span, Op::AssignField(slot));
933                    }
934                    Index(a, b) => {
935                        self.assignable(a, ctx);
936                        self.expression(b, ctx);
937
938                        if mutator(*kind) {
939                            self.add_op(ctx, statement.span, Op::Copy(2));
940                            self.add_op(ctx, statement.span, Op::GetIndex);
941                        }
942                        self.expression(value, ctx);
943                        write_mutator_op(self, ctx, *kind);
944
945                        self.add_op(ctx, statement.span, Op::AssignIndex);
946                    }
947                }
948            }
949
950            StatementExpression { value } => {
951                self.expression(value, ctx);
952                self.add_op(ctx, statement.span, Op::Pop);
953            }
954
955            Block { statements } => {
956                let stack_size = self.frames[ctx.frame].variables.len();
957
958                for statement in statements {
959                    self.statement(statement, ctx);
960                }
961
962                self.pop_until_size(ctx, statement.span, stack_size);
963            }
964
965            Loop { condition, body } => {
966                let start = self.next_ip(ctx);
967                self.expression(condition, ctx);
968                let jump_from = self.add_op(ctx, condition.span, Op::Illegal);
969
970                // Skip the next op - it's for the break
971                //  start: .. condition ..
972                //         JmpFalse(over)
973                //  break: Jmp(end)
974                //   over: .. loop ..
975                //    end: ..
976                self.add_op(ctx, condition.span, Op::Jmp(jump_from + 3));
977                let break_from = self.add_op(ctx, condition.span, Op::Illegal);
978
979                let stack_size = self.frames[ctx.frame].variables.len();
980                self.loops.push(LoopFrame {
981                    continue_addr: start,
982                    break_addr: break_from,
983                    stack_size,
984                });
985                self.statement(body, ctx);
986                self.loops.pop();
987
988                self.add_op(ctx, body.span, Op::Jmp(start));
989                let out = self.next_ip(ctx);
990                self.patch(ctx, jump_from, Op::JmpFalse(out));
991                self.patch(ctx, break_from, Op::Jmp(out));
992            }
993
994            #[rustfmt::skip]
995            If { condition, pass, fail } => {
996                self.expression(condition, ctx);
997
998                let jump_from = self.add_op(ctx, condition.span, Op::Illegal);
999                self.statement(pass, ctx);
1000                let jump_out = self.add_op(ctx, condition.span, Op::Illegal);
1001                self.statement(fail, ctx);
1002
1003                self.patch(ctx, jump_from, Op::JmpFalse(jump_out + 1));
1004
1005                let end = self.next_ip(ctx);
1006                self.patch(ctx, jump_out, Op::Jmp(end));
1007            }
1008
1009            Continue {} => match self.loops.last().cloned() {
1010                Some(LoopFrame { stack_size, continue_addr, .. }) => {
1011                    self.pop_until_size(ctx, statement.span, stack_size);
1012                    self.add_op(ctx, statement.span, Op::Jmp(continue_addr));
1013                }
1014                None => {
1015                    error!(self, ctx, statement.span, "`continue` statement not in a loop");
1016                }
1017            }
1018
1019            Break {} => match self.loops.last().cloned() {
1020                Some(LoopFrame { stack_size, break_addr, .. }) => {
1021                    self.pop_until_size(ctx, statement.span, stack_size);
1022                    self.add_op(ctx, statement.span, Op::Jmp(break_addr));
1023                }
1024                None => {
1025                    error!(self, ctx, statement.span, "`continue` statement not in a loop");
1026                }
1027            }
1028
1029            Unreachable {} => {
1030                self.add_op(ctx, statement.span, Op::Unreachable);
1031            }
1032
1033            Ret { value } => {
1034                self.expression(value, ctx);
1035                self.add_op(ctx, statement.span, Op::Return);
1036            }
1037        }
1038    }
1039
1040    fn module_functions(&mut self, module: &Module, ctx: Context) {
1041        for statement in module.statements.iter() {
1042            match statement.kind {
1043                StatementKind::Definition {
1044                    value:
1045                        Expression {
1046                            kind: ExpressionKind::Function { .. },
1047                            ..
1048                        },
1049                    ..
1050                } => {
1051                    self.statement(statement, ctx);
1052                }
1053                _ => (),
1054            }
1055        }
1056    }
1057
1058    fn module_not_functions(&mut self, module: &Module, ctx: Context) {
1059        for statement in module.statements.iter() {
1060            match statement.kind {
1061                StatementKind::Definition {
1062                    value:
1063                        Expression {
1064                            kind: ExpressionKind::Function { .. },
1065                            ..
1066                        },
1067                    ..
1068                } => (),
1069                _ => {
1070                    self.statement(statement, ctx);
1071                }
1072            }
1073        }
1074    }
1075
1076    fn compile(
1077        mut self,
1078        tree: AST,
1079        functions: &[(String, RustFunction)],
1080    ) -> Result<Prog, Vec<Error>> {
1081        assert!(!tree.modules.is_empty(), "Cannot compile an empty program");
1082        let num_functions = functions.len();
1083        self.functions = functions
1084            .to_vec()
1085            .into_iter()
1086            .enumerate()
1087            .map(|(i, (s, f))| (s, (i, f)))
1088            .collect();
1089        assert_eq!(
1090            num_functions,
1091            self.functions.len(),
1092            "There are {} names and {} extern functions - some extern functions share name",
1093            self.functions.len(),
1094            num_functions
1095        );
1096
1097        let name = "/preamble/";
1098        let mut block = Block::new(name, 0, &tree.modules[0].0);
1099        block.ty = Type::Function(Vec::new(), Box::new(Type::Void));
1100        self.blocks.push(block);
1101        self.frames.push(Frame::new(name, Span::zero()));
1102        let mut ctx = Context {
1103            block_slot: self.blocks.len() - 1,
1104            frame: self.frames.len() - 1,
1105            ..Context::from_namespace(0)
1106        };
1107
1108        let path_to_namespace_id = self.extract_globals(&tree);
1109
1110        for (full_path, module) in tree.modules.iter() {
1111            let path = full_path.file_stem().unwrap().to_str().unwrap();
1112            ctx.namespace = path_to_namespace_id[path];
1113            self.module_functions(module, ctx);
1114        }
1115
1116        for (full_path, module) in tree.modules.iter() {
1117            let path = full_path.file_stem().unwrap().to_str().unwrap();
1118            ctx.namespace = path_to_namespace_id[path];
1119            self.module_not_functions(module, ctx);
1120        }
1121        let module = &tree.modules[0].1;
1122
1123        self.read_identifier("start", Span::zero(), ctx, 0);
1124        self.add_op(ctx, Span::zero(), Op::Call(0));
1125
1126        let nil = self.constant(Value::Nil);
1127        self.add_op(ctx, module.span, nil);
1128        self.add_op(ctx, module.span, Op::Return);
1129
1130        self.pop_frame(ctx);
1131
1132        if self.errors.is_empty() {
1133            Ok(Prog {
1134                blocks: self
1135                    .blocks
1136                    .into_iter()
1137                    .map(|x| Rc::new(RefCell::new(x)))
1138                    .collect(),
1139                functions: functions.iter().map(|(_, f)| *f).collect(),
1140                blobs: self.blobs,
1141                constants: self.constants,
1142                strings: self.strings,
1143            })
1144        } else {
1145            Err(self.errors)
1146        }
1147    }
1148
1149    fn extract_globals(&mut self, tree: &AST) -> HashMap<String, usize> {
1150        let mut full_path_to_namespace_id = HashMap::new();
1151        for (path, _) in tree.modules.iter() {
1152            let slot = full_path_to_namespace_id.len();
1153            match full_path_to_namespace_id.entry(path) {
1154                Entry::Vacant(vac) => {
1155                    vac.insert(slot);
1156                    self.namespaces.push(Namespace::new());
1157                }
1158
1159                Entry::Occupied(_) => {
1160                    error!(
1161                        self,
1162                        Context::from_namespace(slot),
1163                        Span::zero(),
1164                        "Reading file '{}' twice! How?",
1165                        path.display()
1166                    );
1167                }
1168            }
1169        }
1170
1171        self.namespace_id_to_path = full_path_to_namespace_id
1172            .iter()
1173            .map(|(a, b)| (*b, (*a).clone()))
1174            .collect();
1175
1176        let path_to_namespace_id: HashMap<_, _> = full_path_to_namespace_id
1177            .iter()
1178            .map(|(a, b)| (
1179                a.file_stem().unwrap().to_str().unwrap().to_string(),
1180                *b
1181            ))
1182            .collect();
1183
1184        for (path, module) in tree.modules.iter() {
1185            let path = path.file_stem().unwrap().to_str().unwrap();
1186            let slot = path_to_namespace_id[path];
1187            let ctx = Context::from_namespace(slot);
1188
1189            let mut namespace = self.namespaces[slot].clone();
1190            for statement in module.statements.iter() {
1191                use StatementKind::*;
1192                match &statement.kind {
1193                    Blob { name, .. } => match namespace.entry(name.to_owned()) {
1194                        Entry::Vacant(_) => {
1195                            let id = self.blobs.len();
1196                            self.blobs.push(crate::Blob::new(id, slot, name));
1197                            let blob = self.constant(Value::Blob(id));
1198                            if let Op::Constant(slot) = blob {
1199                                namespace.insert(name.to_owned(), Name::Blob(slot));
1200                            } else {
1201                                unreachable!();
1202                            }
1203                        }
1204
1205                        Entry::Occupied(_) => {
1206                            error!(
1207                                self,
1208                                ctx,
1209                                statement.span,
1210                                "A global variable with the name '{}' already exists",
1211                                name
1212                            );
1213                        }
1214                    },
1215
1216                    // Handled below.
1217                    _ => (),
1218                }
1219            }
1220            self.namespaces[slot] = namespace;
1221        }
1222
1223        for (path, module) in tree.modules.iter() {
1224            let path = path.file_stem().unwrap().to_str().unwrap();
1225            let slot = path_to_namespace_id[path];
1226            let ctx = Context::from_namespace(slot);
1227
1228            let mut namespace = self.namespaces[slot].clone();
1229            for statement in module.statements.iter() {
1230                use StatementKind::*;
1231                match &statement.kind {
1232                    Use {
1233                        file: Identifier { name, span },
1234                    } => {
1235                        let other = path_to_namespace_id[name];
1236                        match namespace.entry(name.to_owned()) {
1237                            Entry::Vacant(vac) => {
1238                                vac.insert(Name::Namespace(other));
1239                            }
1240                            Entry::Occupied(_) => {
1241                                error!(
1242                                    self,
1243                                    ctx,
1244                                    *span,
1245                                    "A global variable with the name '{}' already exists",
1246                                    name
1247                                );
1248                            }
1249                        }
1250                    }
1251
1252                    // Already handled in the loop before.
1253                    Blob { .. } => (),
1254
1255                    // Handled in the loop after - so namespaces are structured correctly.
1256                    Definition { .. } => {}
1257
1258                    // Handled later - since we need the type information.
1259                    IsCheck { .. } => (),
1260
1261                    _ => (),
1262                }
1263            }
1264            self.namespaces[slot] = namespace;
1265        }
1266
1267        for (path, module) in tree.modules.iter() {
1268            let path = path.file_stem().unwrap().to_str().unwrap();
1269            let slot = path_to_namespace_id[path];
1270            let ctx = Context::from_namespace(slot);
1271
1272            let mut namespace = self.namespaces[slot].clone();
1273            for statement in module.statements.iter() {
1274                use StatementKind::*;
1275                match &statement.kind {
1276                    #[rustfmt::skip]
1277                    Definition { ident: Identifier { name, .. }, kind, ty, .. } => {
1278                        let var = self.define(name, *kind, statement.span);
1279                        self.activate(var);
1280
1281                        match namespace.entry(name.to_owned()) {
1282                            Entry::Vacant(_) => {
1283                                namespace.insert(name.to_owned(), Name::Global(var));
1284                            }
1285                            Entry::Occupied(_) => {
1286                                error!(
1287                                    self,
1288                                    ctx,
1289                                    statement.span,
1290                                    "A global variable with the name '{}' already exists",
1291                                    name
1292                                );
1293                            }
1294                        }
1295
1296                        // Just fill in an empty slot since we have no idea.
1297                        // Unknown is overwritten by the Op::Force in the type checker.
1298                        let unknown = self.constant(Value::Unknown);
1299                        self.add_op(ctx, Span::zero(), unknown);
1300
1301                        let ty = self.resolve_type(ty, ctx);
1302                        let op = if let Op::Constant(ty) = self.constant(Value::Ty(ty)) {
1303                            Op::Force(ty)
1304                        } else {
1305                            error!(self, ctx, statement.span, "Failed to resolve the type");
1306                            Op::Illegal
1307                        };
1308                        self.add_op(ctx, Span::zero(), op);
1309                    }
1310
1311                    Use { ..  } => { }
1312
1313                    // Already handled in the loop before.
1314                    Blob { .. } => (),
1315
1316                    // Handled later - since we need the type information.
1317                    IsCheck { .. } => (),
1318
1319                    _ => {
1320                        error!(self, ctx, statement.span, "Invalid outer statement");
1321                    }
1322                }
1323            }
1324            self.namespaces[slot] = namespace;
1325        }
1326        path_to_namespace_id
1327    }
1328}
1329
1330pub fn compile(prog: AST, functions: &[(String, RustFunction)]) -> Result<Prog, Vec<Error>> {
1331    Compiler::new().compile(prog, functions)
1332}
1333
1334fn all_paths_return(statement: &Statement) -> bool {
1335    match &statement.kind {
1336        StatementKind::Use { .. }
1337        | StatementKind::Blob { .. }
1338        | StatementKind::IsCheck { .. }
1339        | StatementKind::Print { .. }
1340        | StatementKind::Assignment { .. }
1341        | StatementKind::Definition { .. }
1342        | StatementKind::StatementExpression { .. }
1343        | StatementKind::Unreachable
1344        | StatementKind::Continue
1345        | StatementKind::Break
1346        | StatementKind::EmptyStatement => false,
1347
1348        StatementKind::If { pass, fail, .. } => all_paths_return(pass) && all_paths_return(fail),
1349
1350        StatementKind::Loop { body, .. } => all_paths_return(body),
1351        StatementKind::Block { statements } => statements.iter().any(all_paths_return),
1352
1353        StatementKind::Ret { .. } => true,
1354    }
1355}
sylt_compiler/compiler.rs

sylt_compiler/
compiler.rs
