rune/compile/
ir.rs

Help
1//! Intermediate representation of Rune that can be evaluated in constant
2//! contexts.
3//!
4//! This is part of the [Rune Language](https://rune-rs.github.io).
5
6pub(crate) mod compiler;
7mod eval;
8mod interpreter;
9pub(crate) mod scopes;
10
11use core::ops::{AddAssign, MulAssign, ShlAssign, ShrAssign, SubAssign};
12
13use crate as rune;
14use crate::alloc::prelude::*;
15use crate::alloc::{Box, Vec};
16use crate::ast::{self, Span, Spanned};
17use crate::compile::ir;
18use crate::compile::{self, ItemId, WithSpan};
19use crate::hir;
20use crate::indexing::index;
21use crate::macros::MacroContext;
22use crate::query::Used;
23use crate::runtime::{Inline, Value};
24
25pub(crate) use self::compiler::Ctxt;
26pub(crate) use self::eval::{eval_ir, EvalOutcome};
27pub(crate) use self::interpreter::{Budget, Interpreter};
28pub(crate) use self::scopes::Scopes;
29
30impl ast::Expr {
31    pub(crate) fn eval(&self, cx: &mut MacroContext<'_, '_, '_>) -> compile::Result<Value> {
32        let mut expr = self.try_clone()?;
33        index::expr(cx.idx, &mut expr)?;
34
35        let ir = {
36            // TODO: avoid this arena?
37            let arena = hir::Arena::new();
38
39            let mut hir_ctx =
40                hir::Ctxt::with_const(&arena, cx.idx.q.borrow(), cx.item_meta.location.source_id)?;
41            let hir = hir::lowering::expr(&mut hir_ctx, &expr)?;
42
43            let mut cx = Ctxt {
44                source_id: cx.item_meta.location.source_id,
45                q: cx.idx.q.borrow(),
46            };
47
48            compiler::expr(&hir, &mut cx)?
49        };
50
51        let mut ir_interpreter = Interpreter {
52            budget: Budget::new(1_000_000),
53            scopes: Scopes::new()?,
54            module: cx.item_meta.module,
55            item: cx.item_meta.item,
56            q: cx.idx.q.borrow(),
57        };
58
59        ir_interpreter.eval_value(&ir, Used::Used)
60    }
61}
62
63macro_rules! decl_kind {
64    (
65        $(#[$meta:meta])*
66        $vis:vis enum $name:ident {
67            $($(#[$field_meta:meta])* $variant:ident($ty:ty)),* $(,)?
68        }
69    ) => {
70        $(#[$meta])*
71        $vis enum $name {
72            $($(#[$field_meta])* $variant($ty),)*
73        }
74
75        $(
76            impl From<$ty> for $name {
77                fn from(value: $ty) -> $name {
78                    $name::$variant(value)
79                }
80            }
81        )*
82    }
83}
84
85/// A single operation in the Rune intermediate language.
86#[derive(Debug, TryClone, Spanned)]
87pub(crate) struct Ir {
88    #[rune(span)]
89    pub(crate) span: Span,
90    pub(crate) kind: IrKind,
91}
92
93impl Ir {
94    /// Construct a new intermediate instruction.
95    pub(crate) fn new<S, K>(spanned: S, kind: K) -> Self
96    where
97        S: Spanned,
98        IrKind: From<K>,
99    {
100        Self {
101            span: spanned.span(),
102            kind: IrKind::from(kind),
103        }
104    }
105}
106
107/// The target of a set operation.
108#[derive(Debug, TryClone, Spanned)]
109pub(crate) struct IrTarget {
110    /// Span of the target.
111    #[rune(span)]
112    pub(crate) span: Span,
113    /// Kind of the target.
114    pub(crate) kind: IrTargetKind,
115}
116
117/// The kind of the target.
118#[derive(Debug, TryClone)]
119pub(crate) enum IrTargetKind {
120    /// A variable.
121    Name(hir::Variable),
122    /// A field target.
123    Field(Box<IrTarget>, Box<str>),
124    /// An index target.
125    Index(Box<IrTarget>, usize),
126}
127
128decl_kind! {
129    /// The kind of an intermediate operation.
130    #[derive(Debug, TryClone)]
131    pub(crate) enum IrKind {
132        /// Push a scope with the given instructions.
133        Scope(IrScope),
134        /// A binary operation.
135        Binary(IrBinary),
136        /// Declare a local variable with the value of the operand.
137        Decl(IrDecl),
138        /// Set the given target.
139        Set(IrSet),
140        /// Assign the given target.
141        Assign(IrAssign),
142        /// A template.
143        Template(IrTemplate),
144        /// A named value.
145        Name(hir::Variable),
146        /// A local name. Could either be a local variable or a reference to
147        /// something else, like another const declaration.
148        Target(IrTarget),
149        /// A constant value.
150        Value(Value),
151        /// A sequence of conditional branches.
152        Branches(IrBranches),
153        /// A loop.
154        Loop(IrLoop),
155        /// A break to the given target.
156        Break(IrBreak),
157        /// Constructing a vector.
158        Vec(IrVec),
159        /// Constructing a tuple.
160        Tuple(Tuple),
161        /// Constructing an object.
162        Object(IrObject),
163        /// A call.
164        Call(IrCall),
165    }
166}
167
168/// An interpeted function.
169#[derive(Debug, TryClone, Spanned)]
170pub(crate) struct IrFn {
171    /// The span of the function.
172    #[rune(span)]
173    pub(crate) span: Span,
174    /// The number of arguments the function takes and their names.
175    pub(crate) args: Vec<hir::Variable>,
176    /// The scope for the function.
177    pub(crate) ir: Ir,
178}
179
180impl IrFn {
181    pub(crate) fn compile_ast(
182        hir: &hir::ItemFn<'_>,
183        cx: &mut Ctxt<'_, '_>,
184    ) -> compile::Result<Self> {
185        let mut args = Vec::new();
186
187        for arg in hir.args {
188            if let hir::FnArg::Pat(hir::PatBinding {
189                pat:
190                    hir::Pat {
191                        kind: hir::PatKind::Path(&hir::PatPathKind::Ident(name)),
192                        ..
193                    },
194                ..
195            }) = arg
196            {
197                args.try_push(name)?;
198                continue;
199            }
200
201            return Err(compile::Error::msg(arg, "Unsupported argument in const fn"));
202        }
203
204        let ir_scope = compiler::block(&hir.body, cx)?;
205
206        Ok(ir::IrFn {
207            span: hir.span(),
208            args,
209            ir: ir::Ir::new(hir.span(), ir_scope),
210        })
211    }
212}
213
214/// Definition of a new variable scope.
215#[derive(Debug, TryClone, Spanned)]
216pub(crate) struct IrScope {
217    /// The span of the scope.
218    #[rune(span)]
219    pub(crate) span: Span,
220    /// Instructions in the scope.
221    pub(crate) instructions: Vec<Ir>,
222    /// The implicit value of the scope.
223    pub(crate) last: Option<Box<Ir>>,
224}
225
226/// A binary operation.
227#[derive(Debug, TryClone, Spanned)]
228pub(crate) struct IrBinary {
229    /// The span of the binary op.
230    #[rune(span)]
231    pub(crate) span: Span,
232    /// The binary operation.
233    pub(crate) op: IrBinaryOp,
234    /// The left-hand side of the binary op.
235    pub(crate) lhs: Box<Ir>,
236    /// The right-hand side of the binary op.
237    pub(crate) rhs: Box<Ir>,
238}
239
240/// A local variable declaration.
241#[derive(Debug, TryClone, Spanned)]
242pub(crate) struct IrDecl {
243    /// The span of the declaration.
244    #[rune(span)]
245    pub(crate) span: Span,
246    /// The name of the variable.
247    pub(crate) name: hir::Variable,
248    /// The value of the variable.
249    pub(crate) value: Box<Ir>,
250}
251
252/// Set a target.
253#[derive(Debug, TryClone, Spanned)]
254pub(crate) struct IrSet {
255    /// The span of the set operation.
256    #[rune(span)]
257    pub(crate) span: Span,
258    /// The target to set.
259    pub(crate) target: IrTarget,
260    /// The value to set the target.
261    pub(crate) value: Box<Ir>,
262}
263
264/// Assign a target.
265#[derive(Debug, TryClone, Spanned)]
266pub(crate) struct IrAssign {
267    /// The span of the set operation.
268    #[rune(span)]
269    pub(crate) span: Span,
270    /// The name of the target to assign.
271    pub(crate) target: IrTarget,
272    /// The value to assign.
273    pub(crate) value: Box<Ir>,
274    /// The assign operation.
275    pub(crate) op: IrAssignOp,
276}
277
278/// A string template.
279#[derive(Debug, TryClone, Spanned)]
280pub(crate) struct IrTemplate {
281    /// The span of the template.
282    #[rune(span)]
283    pub(crate) span: Span,
284    /// Template components.
285    pub(crate) components: Vec<IrTemplateComponent>,
286}
287
288/// A string template.
289#[derive(Debug, TryClone)]
290pub(crate) enum IrTemplateComponent {
291    /// An ir expression.
292    Ir(Ir),
293    /// A literal string.
294    String(Box<str>),
295}
296
297/// Branch conditions in intermediate representation.
298#[derive(Debug, TryClone, Spanned)]
299pub(crate) struct IrBranches {
300    /// Span associated with branches.
301    #[rune(span)]
302    pub(crate) span: Span,
303    /// branches and their associated conditions.
304    pub(crate) branches: Vec<(IrCondition, IrScope)>,
305    /// The default fallback branch.
306    pub(crate) default_branch: Option<IrScope>,
307}
308
309/// The condition for a branch.
310#[derive(Debug, TryClone, Spanned)]
311pub(crate) enum IrCondition {
312    /// A simple conditional ir expression.
313    Ir(Ir),
314    /// A pattern match.
315    Let(IrLet),
316}
317
318/// A pattern match.
319#[derive(Debug, TryClone, Spanned)]
320pub(crate) struct IrLet {
321    /// The span of the let condition.
322    #[rune(span)]
323    pub(crate) span: Span,
324    /// The pattern.
325    pub(crate) pat: IrPat,
326    /// The expression the pattern is evaluated on.
327    pub(crate) ir: Ir,
328}
329
330/// A pattern.
331#[derive(Debug, TryClone)]
332pub(crate) enum IrPat {
333    /// An ignore pattern `_`.
334    Ignore,
335    /// A named binding.
336    Binding(hir::Variable),
337}
338
339impl IrPat {
340    fn compile_ast(hir: &hir::Pat<'_>) -> compile::Result<Self> {
341        match hir.kind {
342            hir::PatKind::Ignore => return Ok(ir::IrPat::Ignore),
343            hir::PatKind::Path(&hir::PatPathKind::Ident(name)) => {
344                return Ok(ir::IrPat::Binding(name));
345            }
346            _ => (),
347        }
348
349        Err(compile::Error::msg(hir, "pattern not supported yet"))
350    }
351
352    fn matches<S>(
353        &self,
354        interp: &mut Interpreter<'_, '_>,
355        value: Value,
356        spanned: S,
357    ) -> Result<bool, ir::EvalOutcome>
358    where
359        S: Spanned,
360    {
361        match self {
362            IrPat::Ignore => Ok(true),
363            IrPat::Binding(name) => {
364                interp.scopes.decl(*name, value).with_span(spanned)?;
365                Ok(true)
366            }
367        }
368    }
369}
370
371/// A loop with an optional condition.
372#[derive(Debug, TryClone, Spanned)]
373pub(crate) struct IrLoop {
374    /// The span of the loop.
375    #[rune(span)]
376    pub(crate) span: Span,
377    /// The label of the loop.
378    pub(crate) label: Option<Box<str>>,
379    /// The condition of the loop.
380    pub(crate) condition: Option<Box<IrCondition>>,
381    /// The body of the loop.
382    pub(crate) body: IrScope,
383}
384
385/// A break operation.
386#[derive(Debug, TryClone, Spanned)]
387pub(crate) struct IrBreak {
388    /// The span of the break.
389    #[rune(span)]
390    pub(crate) span: Span,
391    /// The label of the break.
392    pub(crate) label: Option<Box<str>>,
393    /// The value of the break.
394    pub(crate) expr: Option<Box<Ir>>,
395}
396
397impl IrBreak {
398    fn compile_ast(
399        span: Span,
400        cx: &mut Ctxt<'_, '_>,
401        hir: &hir::ExprBreak,
402    ) -> compile::Result<Self> {
403        let label = hir.label.map(TryInto::try_into).transpose()?;
404
405        let expr = match hir.expr {
406            Some(e) => Some(Box::try_new(compiler::expr(e, cx)?)?),
407            None => None,
408        };
409
410        Ok(ir::IrBreak { span, label, expr })
411    }
412
413    /// Evaluate the break into an [ir::EvalOutcome].
414    fn as_outcome(&self, interp: &mut Interpreter<'_, '_>, used: Used) -> ir::EvalOutcome {
415        let span = self.span();
416
417        if let Err(e) = interp.budget.take(span) {
418            return e.into();
419        }
420
421        let expr = match &self.expr {
422            Some(ir) => match ir::eval_ir(ir, interp, used) {
423                Ok(value) => Some(value),
424                Err(err) => return err,
425            },
426            None => None,
427        };
428
429        let label = match self.label.try_clone() {
430            Ok(label) => label,
431            Err(error) => return error.into(),
432        };
433
434        ir::EvalOutcome::Break(span, label, expr)
435    }
436}
437
438/// Tuple expression.
439#[derive(Debug, TryClone, Spanned)]
440pub(crate) struct Tuple {
441    /// Span of the tuple.
442    #[rune(span)]
443    pub(crate) span: Span,
444    /// Arguments to construct the tuple.
445    pub(crate) items: Box<[Ir]>,
446}
447
448/// Object expression.
449#[derive(Debug, TryClone, Spanned)]
450pub(crate) struct IrObject {
451    /// Span of the object.
452    #[rune(span)]
453    pub(crate) span: Span,
454    /// Field initializations.
455    pub(crate) assignments: Box<[(Box<str>, Ir)]>,
456}
457
458/// Call expressions.
459#[derive(Debug, TryClone, Spanned)]
460pub(crate) struct IrCall {
461    /// Span of the call.
462    #[rune(span)]
463    pub(crate) span: Span,
464    /// Arguments to the call.
465    pub(crate) args: Vec<Ir>,
466    /// The target of the call.
467    pub(crate) id: ItemId,
468}
469
470/// Vector expression.
471#[derive(Debug, TryClone, Spanned)]
472pub(crate) struct IrVec {
473    /// Span of the vector.
474    #[rune(span)]
475    pub(crate) span: Span,
476    /// Arguments to construct the vector.
477    pub(crate) items: Box<[Ir]>,
478}
479
480/// A binary operation.
481#[derive(Debug, TryClone, Clone, Copy)]
482#[try_clone(copy)]
483pub(crate) enum IrBinaryOp {
484    /// Add `+`.
485    Add,
486    /// Subtract `-`.
487    Sub,
488    /// Multiplication `*`.
489    Mul,
490    /// Division `/`.
491    Div,
492    /// `<<`.
493    Shl,
494    /// `>>`.
495    Shr,
496    /// `<`,
497    Lt,
498    /// `<=`,
499    Lte,
500    /// `==`,
501    Eq,
502    /// `>`,
503    Gt,
504    /// `>=`,
505    Gte,
506}
507
508/// An assign operation.
509#[derive(Debug, TryClone, Clone, Copy)]
510#[try_clone(copy)]
511pub(crate) enum IrAssignOp {
512    /// `+=`.
513    Add,
514    /// `-=`.
515    Sub,
516    /// `*=`.
517    Mul,
518    /// `/=`.
519    Div,
520    /// `<<=`.
521    Shl,
522    /// `>>=`.
523    Shr,
524}
525
526impl IrAssignOp {
527    /// Perform the given assign operation.
528    pub(crate) fn assign<S>(
529        self,
530        spanned: S,
531        target: &mut Value,
532        operand: Value,
533    ) -> compile::Result<()>
534    where
535        S: Copy + Spanned,
536    {
537        if let Some(Inline::Signed(target)) = target.as_inline_mut() {
538            if let Some(Inline::Signed(operand)) = operand.as_inline() {
539                return self.assign_int(spanned, target, *operand);
540            }
541        }
542
543        Err(compile::Error::msg(spanned, "unsupported operands"))
544    }
545
546    /// Perform the given assign operation.
547    fn assign_int<S>(self, spanned: S, target: &mut i64, operand: i64) -> compile::Result<()>
548    where
549        S: Copy + Spanned,
550    {
551        match self {
552            IrAssignOp::Add => {
553                target.add_assign(operand);
554            }
555            IrAssignOp::Sub => {
556                target.sub_assign(operand);
557            }
558            IrAssignOp::Mul => {
559                target.mul_assign(operand);
560            }
561            IrAssignOp::Div => {
562                *target = target
563                    .checked_div(operand)
564                    .ok_or("division by zero")
565                    .with_span(spanned)?;
566            }
567            IrAssignOp::Shl => {
568                let operand = u32::try_from(operand)
569                    .map_err(|_| "bad operand")
570                    .with_span(spanned)?;
571
572                target.shl_assign(operand);
573            }
574            IrAssignOp::Shr => {
575                let operand = u32::try_from(operand)
576                    .map_err(|_| "bad operand")
577                    .with_span(spanned)?;
578
579                target.shr_assign(operand);
580            }
581        }
582
583        Ok(())
584    }
585}
rune/compile/ir.rs

rune/compile/
ir.rs
