nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
74 kB
2149 lines
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2025 The Gleam contributors
3
4//! This module implements the function inlining optimisation. This allows
5//! function calls to be inlined at the callsite, and replaced with the contents
6//! of the function which is being called.
7//!
8//! Function inlining is useful for two main reasons:
9//! - It removes the overhead of calling other functions and jumping around
10//! execution too much
11//! - It removes the barrier of the function call between the code around the
12//! call, and the code inside the called function.
13//!
14//! For example, the following Gleam code make heavy use of `use` sugar and higher
15//! order functions:
16//!
17//! ```gleam
18//! pub fn try_sum(list: List(Result(String, Nil)), sum: Int) -> Result(Int, Nil) {
19//! use <- bool.guard(when: sum >= 1000, return: Ok(sum))
20//! case list {
21//! [] -> Ok(sum)
22//! [first, ..rest] -> {
23//! use number <- result.try(int.parse(first))
24//! try_sum(rest, sum + number)
25//! }
26//! }
27//! }
28//! ```
29//!
30//! This can make the code easier to read, but it normally would have a performance
31//! cost. There are two called functions, and two implicit anonymous functions.
32//! This function is also not tail recursive, as it uses higher order functions
33//! inside its body.
34//!
35//! However, with function inlining, the above code can be optimised to:
36//!
37//! ```gleam
38//! pub fn try_sum(list: List(Result(String, Nil)), sum: Int) -> Result(Int, Nil) {
39//! case sum >= 1000 {
40//! True -> Ok(sum)
41//! False -> case list {
42//! [] -> Ok(sum)
43//! [first, ..rest] -> {
44//! case int.parse(first) {
45//! Ok(number) -> try_sum(rest, sum + number)
46//! Error(error) -> Error(error)
47//! }
48//! }
49//! }
50//! }
51//! }
52//! ```
53//!
54//! Which now has no extra function calls, and is tail recursive!
55//!
56//! The process of function inlining is quite simple really. It is implemented
57//! using an AST folder, which traverses each node of the AST, and potentially
58//! alters it as it goes.
59//!
60//! Every time we encounter a function call, we decide whether or not we can
61//! inline it. For now, the criteria for inlining is very simple, although a
62//! more complex heuristic-based approach will likely be implemented in the
63//! future. For now though, a function can be inlined if:
64//! It is a standard library function within the hardcoded list - which can be
65//! found in the `inline_function` function - or, it is an anonymous function.
66//!
67//! Inlining anonymous functions allows us to:
68//! - Remove calls to parameters of higher-order functions once those higher-
69//! order functions have been inlined. For example, the following example using
70//! `result.map`:
71//! ```gleam
72//! result.map(Ok(10), fn(x) { x + 1 })
73//! ```
74//!
75//! Without inlining of anonymous function would be turned into:
76//! ```gleam
77//! case Ok(10) {
78//! Ok(value) -> Ok(fn(x) { x + 1 }(value))
79//! Error(error) -> Error(error)
80//! }
81//! ```
82//!
83//! However if we inline anonymous functions also, we remove every call, and
84//! so it becomes:
85//!
86//! ```gleam
87//! case Ok(10) {
88//! Ok(value) -> Ok(value + 1)
89//! Error(error) -> Error(error)
90//! }
91//! ```
92//!
93//! - Remove calls to anonymous functions in pipelines. Sometimes, an anonymous
94//! function is used in a pipeline, which can sometimes be the result of an
95//! expanded function capture. For example:
96//!
97//! ```gleam
98//! "10" |> int.parse |> result.unwrap(0) |> fn(x) { x * x } |> something_else
99//! ```
100//!
101//! This can now be desugared to:
102//! ```gleam
103//! let _pipe1 = "10"
104//! let _pipe2 = int.parse(_pipe1)
105//! let _pipe3 = result.unwrap(_pipe2, 0)
106//! let _pipe4 = _pipe3 * _pipe3
107//! something_else(_pipe4)
108//! ```
109//!
110//! See documentation of individual functions to explain better how the process
111//! works.
112//!
113
114#![allow(dead_code)]
115
116use std::{
117 collections::{HashMap, HashSet},
118 sync::Arc,
119};
120
121use ecow::{EcoString, eco_format};
122use itertools::Itertools;
123use vec1::Vec1;
124
125use crate::{
126 STDLIB_PACKAGE_NAME,
127 analyse::Inferred,
128 ast::{
129 self, ArgNames, Assert, AssignName, Assignment, AssignmentKind, BitArrayOption,
130 BitArraySegment, BitArraySize, CallArg, Clause, FunctionLiteralKind, Pattern,
131 PipelineAssignmentKind, Publicity, SrcSpan, Statement, TailPattern, TypedArg, TypedAssert,
132 TypedAssignment, TypedBitArraySize, TypedClause, TypedDefinitions, TypedExpr,
133 TypedExprBitArraySegment, TypedFunction, TypedModule, TypedPattern,
134 TypedPipelineAssignment, TypedStatement, TypedUse, visit::Visit,
135 },
136 exhaustiveness::{Body, CompiledCase, Decision},
137 type_::{
138 self, Deprecation, ModuleInterface, ModuleValueConstructor, PRELUDE_MODULE_NAME,
139 PatternConstructor, Type, TypedCallArg, ValueConstructor, ValueConstructorVariant,
140 collapse_links,
141 error::VariableOrigin,
142 expression::{Implementations, Purity},
143 },
144};
145
146/// Perform function inlining across an entire module, applying it to each
147/// individual function.
148pub fn module(
149 mut module: TypedModule,
150 modules: &im::HashMap<EcoString, ModuleInterface>,
151) -> TypedModule {
152 let mut inliner = Inliner::new(modules);
153
154 module.definitions = TypedDefinitions {
155 functions: module
156 .definitions
157 .functions
158 .into_iter()
159 .map(|function| inliner.function(function))
160 .collect(),
161 ..module.definitions
162 };
163
164 module
165}
166
167struct Inliner<'a> {
168 /// Importable modules, containing information about functions which can be
169 /// inlined
170 modules: &'a im::HashMap<EcoString, ModuleInterface>,
171 /// Any variables which can be inlined. This is used when inlining the body
172 /// of function calls. Let's look at an example inlinable function:
173 /// ```gleam
174 /// pub fn add(a, b) {
175 /// a + b
176 /// }
177 /// ```
178 /// If it is called - `add(1, 2)` - it can be inlined to the following:
179 /// ```gleam
180 /// {
181 /// let a = 1
182 /// let b = 2
183 /// a + b
184 /// }
185 /// ```
186 ///
187 /// However, this can be inlined further. Since `a` and `b` are only used
188 /// once each in the body, the whole expression can be reduced to `1 + 2`.
189 ///
190 /// In the above example, this variable would contain `{a: 1, b: 2}`,
191 /// indicating the names of the variables to be inlined, as well as the
192 /// values to replace them with.
193 inline_variables: HashMap<EcoString, TypedExpr>,
194
195 /// The number we append to variable names in order to ensure uniqueness.
196 variable_number: usize,
197 /// Set of in-scope variables, used to determine when a conflict between
198 /// variable names occurs during inlining.
199 in_scope: HashSet<EcoString>,
200 /// If two variables conflict in names during inlining, we need to rename
201 /// one to avoid the conflict. Any variables renamed this way are stored
202 /// here.
203 renamed_variables: im::HashMap<EcoString, EcoString>,
204 /// The current position, whether we are inside the body of an inlined
205 /// function or not.
206 position: Position,
207}
208
209#[derive(Debug, Clone, Copy, PartialEq)]
210enum Position {
211 RegularFunction,
212 InlinedFunction,
213}
214
215impl Inliner<'_> {
216 fn new(modules: &im::HashMap<EcoString, ModuleInterface>) -> Inliner<'_> {
217 Inliner {
218 modules,
219 inline_variables: HashMap::new(),
220 variable_number: 0,
221 renamed_variables: im::HashMap::new(),
222 in_scope: HashSet::new(),
223 position: Position::RegularFunction,
224 }
225 }
226
227 /// Defines a variable in the current scope, renaming it if necessary.
228 /// Currently, this duplicates work performed in the code generators, where
229 /// variables are renamed in a similar way. But since inlining can change
230 /// scope boundaries, it needs to be performed here too. Ideally, we would
231 /// move all the deduplicating logic from the code generators to here where
232 /// we perform inlining, but that is a fairly large item of work.
233 fn define_variable(&mut self, name: EcoString) -> EcoString {
234 let unique_in_scope = self.in_scope.insert(name.clone());
235 // If the variable name is already defined, and we are inlining a function,
236 // that means there is a potential conflict in names and we need to rename
237 // the variable.
238 if !unique_in_scope && self.position == Position::InlinedFunction {
239 // Prefixing the variable name with `_inline_` ensures it does
240 // not conflict with other defined variables.
241 let new_name = eco_format!("_inline_{name}_{}", self.variable_number);
242 self.variable_number += 1;
243 _ = self.renamed_variables.insert(name, new_name.clone());
244 new_name
245 } else {
246 name
247 }
248 }
249
250 /// Get the name we are using for a variable, in case it is renamed.
251 fn variable_name(&self, name: EcoString) -> EcoString {
252 self.renamed_variables.get(&name).cloned().unwrap_or(name)
253 }
254
255 fn function(&mut self, mut function: TypedFunction) -> TypedFunction {
256 for argument in function.arguments.iter() {
257 match &argument.names {
258 ArgNames::Discard { .. } | ArgNames::LabelledDiscard { .. } => {}
259 ArgNames::Named { name, .. } | ArgNames::NamedLabelled { name, .. } => {
260 _ = self.in_scope.insert(name.clone());
261 }
262 }
263 }
264
265 function.body = function
266 .body
267 .into_iter()
268 .map(|statement| self.statement(statement))
269 .collect_vec();
270 function
271 }
272
273 fn statement(&mut self, statement: TypedStatement) -> TypedStatement {
274 match statement {
275 Statement::Expression(expression_ast) => {
276 Statement::Expression(self.expression(expression_ast))
277 }
278 Statement::Assignment(assignment_ast) => {
279 Statement::Assignment(Box::new(self.assignment(*assignment_ast)))
280 }
281 Statement::Use(use_ast) => Statement::Use(self.use_(use_ast)),
282 Statement::Assert(assert_ast) => Statement::Assert(self.assert(assert_ast)),
283 }
284 }
285
286 fn assert(&mut self, assert: TypedAssert) -> TypedAssert {
287 let Assert {
288 location,
289 value,
290 message,
291 } = assert;
292
293 Assert {
294 location,
295 value: self.expression(value),
296 message: message.map(|expression| self.expression(expression)),
297 }
298 }
299
300 fn use_(&mut self, mut use_: TypedUse) -> TypedUse {
301 use_.call = self.boxed_expression(use_.call);
302 use_
303 }
304
305 fn assignment(&mut self, assignment: TypedAssignment) -> TypedAssignment {
306 let Assignment {
307 location,
308 value,
309 pattern,
310 kind,
311 annotation,
312 compiled_case,
313 } = assignment;
314
315 Assignment {
316 location,
317 value: self.expression(value),
318 pattern: self.register_pattern_variables(pattern),
319 kind: self.assignment_kind(kind),
320 annotation,
321 compiled_case,
322 }
323 }
324
325 /// Register variables defined in a pattern so we correctly keep track of
326 /// the scope, and rename any which conflict with existing variables.
327 fn register_pattern_variables(&mut self, pattern: TypedPattern) -> TypedPattern {
328 match pattern {
329 Pattern::Int { .. }
330 | Pattern::Float { .. }
331 | Pattern::String { .. }
332 | Pattern::Discard { .. }
333 | Pattern::Invalid { .. } => pattern,
334
335 Pattern::Variable {
336 location,
337 name,
338 type_,
339 origin,
340 } => Pattern::Variable {
341 location,
342 name: self.define_variable(name),
343 type_,
344 origin,
345 },
346 Pattern::BitArraySize(size) => Pattern::BitArraySize(self.bit_array_size(size)),
347 Pattern::Assign {
348 name,
349 location,
350 pattern,
351 } => Pattern::Assign {
352 name: self.define_variable(name),
353 location,
354 pattern: Box::new(self.register_pattern_variables(*pattern)),
355 },
356 Pattern::List {
357 location,
358 elements,
359 tail,
360 type_,
361 } => Pattern::List {
362 location,
363 elements: elements
364 .into_iter()
365 .map(|element| self.register_pattern_variables(element))
366 .collect(),
367 tail: tail.map(|tail| {
368 Box::new(TailPattern {
369 location: tail.location,
370 pattern: self.register_pattern_variables(tail.pattern),
371 })
372 }),
373 type_,
374 },
375 Pattern::Constructor {
376 location,
377 name_location,
378 name,
379 arguments,
380 module,
381 constructor,
382 spread,
383 type_,
384 } => Pattern::Constructor {
385 location,
386 name_location,
387 name,
388 arguments: arguments
389 .into_iter()
390 .map(
391 |CallArg {
392 label,
393 location,
394 value,
395 implicit,
396 }| CallArg {
397 label,
398 location,
399 value: self.register_pattern_variables(value),
400 implicit,
401 },
402 )
403 .collect(),
404 module,
405 constructor,
406 spread,
407 type_,
408 },
409 Pattern::Tuple { location, elements } => Pattern::Tuple {
410 location,
411 elements: elements
412 .into_iter()
413 .map(|element| self.register_pattern_variables(element))
414 .collect(),
415 },
416 Pattern::BitArray { location, segments } => Pattern::BitArray {
417 location,
418 segments: segments
419 .into_iter()
420 .map(|segment| {
421 self.bit_array_segment(segment, Self::register_pattern_variables)
422 })
423 .collect(),
424 },
425 Pattern::StringPrefix {
426 location,
427 left_location,
428 left_side_assignment,
429 right_location,
430 left_side_string,
431 right_side_assignment,
432 } => Pattern::StringPrefix {
433 location,
434 left_location,
435 left_side_assignment: left_side_assignment
436 .map(|(name, location)| (self.define_variable(name), location)),
437 right_location,
438 left_side_string,
439 right_side_assignment: match right_side_assignment {
440 AssignName::Variable(name) => AssignName::Variable(self.define_variable(name)),
441 AssignName::Discard(name) => AssignName::Discard(name),
442 },
443 },
444 }
445 }
446
447 fn bit_array_size(&mut self, size: TypedBitArraySize) -> TypedBitArraySize {
448 match size {
449 BitArraySize::Int { .. } => size,
450 BitArraySize::Variable {
451 location,
452 name,
453 constructor,
454 type_,
455 } => BitArraySize::Variable {
456 location,
457 name: self.variable_name(name),
458 constructor,
459 type_,
460 },
461 BitArraySize::BinaryOperator {
462 location,
463 operator,
464 left,
465 right,
466 } => BitArraySize::BinaryOperator {
467 location,
468 operator,
469 left: Box::new(self.bit_array_size(*left)),
470 right: Box::new(self.bit_array_size(*right)),
471 },
472 BitArraySize::Block { location, inner } => BitArraySize::Block {
473 location,
474 inner: Box::new(self.bit_array_size(*inner)),
475 },
476 }
477 }
478
479 fn assignment_kind(&mut self, kind: AssignmentKind<TypedExpr>) -> AssignmentKind<TypedExpr> {
480 match kind {
481 AssignmentKind::Let | AssignmentKind::Generated => kind,
482 AssignmentKind::Assert {
483 location,
484 assert_keyword_start,
485 message,
486 } => AssignmentKind::Assert {
487 location,
488 assert_keyword_start,
489 message: message.map(|expression| self.expression(expression)),
490 },
491 }
492 }
493
494 fn boxed_expression(&mut self, boxed: Box<TypedExpr>) -> Box<TypedExpr> {
495 Box::new(self.expression(*boxed))
496 }
497
498 fn expressions(&mut self, expressions: Vec<TypedExpr>) -> Vec<TypedExpr> {
499 expressions
500 .into_iter()
501 .map(|expression| self.expression(expression))
502 .collect()
503 }
504
505 /// Perform inlining over an expression. This function is recursive, as
506 /// expressions can be deeply nested. Most expressions just recursively
507 /// call this function on each of their component parts, but some have
508 /// special handling.
509 fn expression(&mut self, mut expression: TypedExpr) -> TypedExpr {
510 match expression {
511 TypedExpr::Int { .. }
512 | TypedExpr::Float { .. }
513 | TypedExpr::String { .. }
514 | TypedExpr::Fn { .. }
515 | TypedExpr::ModuleSelect { .. }
516 | TypedExpr::Invalid { .. } => expression,
517
518 TypedExpr::Var {
519 ref constructor,
520 ref mut name,
521 ..
522 } => match &constructor.variant {
523 // If this variable can be inlined, replace it with its value.
524 // See the `inline_variables` documentation for an explanation.
525 ValueConstructorVariant::LocalVariable { .. } => {
526 // We remove the variable as inlined variables can only be
527 // inlined once. `inline_variables` only contains variables
528 // which we have already checked are possible to inline, as
529 // we check for variables which are only used once when converting
530 // to an `InlinableFunction`.
531 match self.inline_variables.remove(name) {
532 Some(inlined_expression) => inlined_expression,
533 None => match self.renamed_variables.get(name) {
534 Some(new_name) => {
535 *name = new_name.clone();
536 expression
537 }
538 None => expression,
539 },
540 }
541 }
542 ValueConstructorVariant::ModuleConstant { .. }
543 | ValueConstructorVariant::ModuleFn { .. }
544 | ValueConstructorVariant::Record { .. } => expression,
545 },
546
547 TypedExpr::Block {
548 location,
549 statements,
550 } => TypedExpr::Block {
551 location,
552 statements: statements.mapped(|statement| self.statement(statement)),
553 },
554
555 TypedExpr::NegateBool { location, value } => TypedExpr::NegateBool {
556 location,
557 value: self.boxed_expression(value),
558 },
559
560 TypedExpr::NegateInt { location, value } => TypedExpr::NegateInt {
561 location,
562 value: self.boxed_expression(value),
563 },
564
565 TypedExpr::Pipeline {
566 location,
567 first_value,
568 assignments,
569 finally,
570 finally_kind,
571 } => self.pipeline(location, first_value, assignments, finally, finally_kind),
572
573 TypedExpr::List {
574 location,
575 type_,
576 elements,
577 tail,
578 } => TypedExpr::List {
579 location,
580 type_,
581 elements: self.expressions(elements),
582 tail: tail.map(|boxed_expression| self.boxed_expression(boxed_expression)),
583 },
584
585 TypedExpr::Call {
586 location,
587 type_,
588 fun,
589 arguments,
590 open_parenthesis,
591 } => self.call(location, type_, fun, arguments, open_parenthesis),
592
593 TypedExpr::BinOp {
594 location,
595 type_,
596 operator,
597 operator_start,
598 left,
599 right,
600 } => TypedExpr::BinOp {
601 location,
602 type_,
603 operator,
604 operator_start,
605 left: self.boxed_expression(left),
606 right: self.boxed_expression(right),
607 },
608
609 TypedExpr::Case {
610 location,
611 type_,
612 subjects,
613 clauses,
614 compiled_case,
615 } => self.case(location, type_, subjects, clauses, compiled_case),
616
617 TypedExpr::RecordAccess {
618 location,
619 field_start,
620 type_,
621 label,
622 index,
623 record,
624 documentation,
625 } => TypedExpr::RecordAccess {
626 location,
627 field_start,
628 type_,
629 label,
630 index,
631 record: self.boxed_expression(record),
632 documentation,
633 },
634
635 TypedExpr::PositionalAccess {
636 location,
637 type_,
638 index,
639 record,
640 } => TypedExpr::PositionalAccess {
641 location,
642 type_,
643 index,
644 record: self.boxed_expression(record),
645 },
646
647 TypedExpr::Tuple {
648 location,
649 type_,
650 elements,
651 } => TypedExpr::Tuple {
652 location,
653 type_,
654 elements: self.expressions(elements),
655 },
656
657 TypedExpr::TupleIndex {
658 location,
659 type_,
660 index,
661 tuple,
662 } => TypedExpr::TupleIndex {
663 location,
664 type_,
665 index,
666 tuple: self.boxed_expression(tuple),
667 },
668
669 TypedExpr::Todo {
670 location,
671 message,
672 kind,
673 type_,
674 } => TypedExpr::Todo {
675 location,
676 message: message.map(|boxed_expression| self.boxed_expression(boxed_expression)),
677 kind,
678 type_,
679 },
680
681 TypedExpr::Panic {
682 location,
683 message,
684 type_,
685 } => TypedExpr::Panic {
686 location,
687 message: message.map(|boxed_expression| self.boxed_expression(boxed_expression)),
688 type_,
689 },
690
691 TypedExpr::Echo {
692 location,
693 type_,
694 expression,
695 message,
696 } => TypedExpr::Echo {
697 location,
698 expression: expression.map(|expression| self.boxed_expression(expression)),
699 message: message.map(|message| self.boxed_expression(message)),
700 type_,
701 },
702
703 TypedExpr::BitArray {
704 location,
705 type_,
706 segments,
707 } => self.bit_array(location, type_, segments),
708
709 TypedExpr::RecordUpdate {
710 location,
711 spread_start,
712 type_,
713 updated_record,
714 updated_record_assigned_name,
715 constructor,
716 arguments,
717 } => TypedExpr::RecordUpdate {
718 location,
719 spread_start,
720 type_,
721 updated_record: Box::new(self.expression(*updated_record)),
722 updated_record_assigned_name,
723 constructor: self.boxed_expression(constructor),
724 arguments: self.arguments(arguments),
725 },
726 }
727 }
728
729 fn arguments(&mut self, arguments: Vec<TypedCallArg>) -> Vec<TypedCallArg> {
730 arguments
731 .into_iter()
732 .map(
733 |TypedCallArg {
734 label,
735 location,
736 value,
737 implicit,
738 }| TypedCallArg {
739 label,
740 location,
741 value: self.expression(value),
742 implicit,
743 },
744 )
745 .collect()
746 }
747
748 /// Where the magic happens. First, we check the left-hand side of the call
749 /// to see if it's something we can inline. If not, we continue to walk the
750 /// tree like all the other expressions do. If it can be inlined, we follow
751 /// a three-step process:
752 ///
753 /// - Inlining: Here, we replace the reference to the function with an
754 /// anonymous function with the same contents. If the left-hand side is
755 /// already an anonymous function, we skip this step.
756 ///
757 /// - Beta reduction: The call to the anonymous function it transformed into
758 /// a block with assignments for each argument at the beginning
759 ///
760 /// - Optimisation: We then recursively optimise the block. This allows us
761 /// to, for example, inline anonymous functions passed to higher-order
762 /// functions.
763 ///
764 /// Here is an example of inlining `result.map`:
765 ///
766 /// Initial code:
767 /// ```gleam
768 /// let x = Ok(10)
769 /// result.map(x, fn(x) {
770 /// let y = x + 4
771 /// int.to_string(y)
772 /// })
773 /// ```
774 ///
775 /// After inlining:
776 /// ```gleam
777 /// let x = Ok(10)
778 /// fn(result, function) {
779 /// case result {
780 /// Ok(value) -> Ok(function(value))
781 /// Error(error) -> Error(error)
782 /// }
783 /// }(x, fn(x) {
784 /// let y = x + 4
785 /// int.to_string(y)
786 /// })
787 /// ```
788 ///
789 /// After beta reduction:
790 /// ```gleam
791 /// let x = Ok(10)
792 /// {
793 /// let result = x
794 /// let function = fn(x) {
795 /// let y = x + 4
796 /// int.to_string(y)
797 /// }
798 /// case result {
799 /// Ok(value) -> Ok(function(value))
800 /// Error(error) -> Error(error)
801 /// }
802 /// }
803 /// ```
804 ///
805 /// And finally, after the final optimising pass, where this inlining process
806 /// is repeated:
807 /// ```gleam
808 /// let x = Ok(10)
809 /// case x {
810 /// Ok(value) -> Ok({
811 /// let y = x + 4
812 /// int.to_string(y)
813 /// })
814 /// Error(error) -> Error(error)
815 /// }
816 /// ```
817 ///
818 fn call(
819 &mut self,
820 location: SrcSpan,
821 type_: Arc<Type>,
822 function: Box<TypedExpr>,
823 arguments: Vec<TypedCallArg>,
824 open_parenthesis: Option<u32>,
825 ) -> TypedExpr {
826 let arguments = self.arguments(arguments);
827
828 // First, we traverse the left-hand side of this call. If this is called
829 // inside another inlined function, this could potentially inline an
830 // argument, allowing further inlining.
831 let function = self.expression(*function);
832
833 // If the left-hand side is in a block for some reason, for example
834 // `{ fn(x) { x + 1 } }(10)`, we still want to be able to inline it.
835 let function = expand_block(function);
836
837 let function = match function {
838 TypedExpr::Var {
839 ref constructor,
840 ref name,
841 ..
842 } => match &constructor.variant {
843 ValueConstructorVariant::ModuleFn { module, .. } => {
844 // If the function is in the list of inlinable functions in
845 // the module it belongs to, we can inline it!
846 if let Some(function) = self
847 .modules
848 .get(module)
849 .and_then(|module| module.inline_functions.get(name))
850 {
851 // First, we do the actual inlining, by converting it to
852 // an anonymous function.
853 let (parameters, body) = function.to_anonymous_function();
854 // Then, we perform beta reduction, inlining the call to
855 // the anonymous function.
856 return self.inline_anonymous_function_call(
857 ¶meters,
858 arguments,
859 body,
860 &function.inlinable_parameters,
861 );
862 } else {
863 function
864 }
865 }
866 // We cannot inline local variables or constants, as we do not
867 // have enough information to inline them. Records are not actually
868 // function calls, so they also cannot be inlined.
869 ValueConstructorVariant::LocalVariable { .. }
870 | ValueConstructorVariant::ModuleConstant { .. }
871 | ValueConstructorVariant::Record { .. } => function,
872 },
873 TypedExpr::ModuleSelect {
874 ref constructor,
875 label: ref name,
876 ref module_name,
877 ..
878 } => match constructor {
879 // We use the same logic here as for `TypedExpr::Var` above.
880 ModuleValueConstructor::Fn { .. } => {
881 if let Some(function) = self
882 .modules
883 .get(module_name)
884 .and_then(|module| module.inline_functions.get(name))
885 {
886 let (parameters, body) = function.to_anonymous_function();
887 return self.inline_anonymous_function_call(
888 ¶meters,
889 arguments,
890 body,
891 &function.inlinable_parameters,
892 );
893 } else {
894 function
895 }
896 }
897 ModuleValueConstructor::Record { .. } | ModuleValueConstructor::Constant { .. } => {
898 function
899 }
900 },
901 // Direct calls to anonymous functions can always be inlined
902 TypedExpr::Fn {
903 arguments: parameters,
904 body,
905 ..
906 } => {
907 let inlinable_parameters = find_inlinable_parameters(¶meters, &body);
908 return self.inline_anonymous_function_call(
909 ¶meters,
910 arguments,
911 body,
912 &inlinable_parameters,
913 );
914 }
915 TypedExpr::Int { .. }
916 | TypedExpr::Float { .. }
917 | TypedExpr::String { .. }
918 | TypedExpr::Block { .. }
919 | TypedExpr::Pipeline { .. }
920 | TypedExpr::List { .. }
921 | TypedExpr::Call { .. }
922 | TypedExpr::BinOp { .. }
923 | TypedExpr::Case { .. }
924 | TypedExpr::RecordAccess { .. }
925 | TypedExpr::PositionalAccess { .. }
926 | TypedExpr::Tuple { .. }
927 | TypedExpr::TupleIndex { .. }
928 | TypedExpr::Todo { .. }
929 | TypedExpr::Panic { .. }
930 | TypedExpr::Echo { .. }
931 | TypedExpr::BitArray { .. }
932 | TypedExpr::RecordUpdate { .. }
933 | TypedExpr::NegateBool { .. }
934 | TypedExpr::NegateInt { .. }
935 | TypedExpr::Invalid { .. } => function,
936 };
937
938 TypedExpr::Call {
939 location,
940 type_,
941 fun: Box::new(function),
942 arguments,
943 open_parenthesis,
944 }
945 }
946
947 /// Turn a call to an anonymous function into a block with assignments.
948 fn inline_anonymous_function_call(
949 &mut self,
950 parameters: &[TypedArg],
951 arguments: Vec<TypedCallArg>,
952 body: Vec1<TypedStatement>,
953 inlinable_parameters: &[EcoString],
954 ) -> TypedExpr {
955 // Arguments to this call that can be inlined, and do not need an assignment.
956 let mut inline = HashMap::new();
957
958 // We start by collecting all the assignments for parameters which cannot
959 // be inlined.
960 let mut statements = parameters
961 .iter()
962 .zip(arguments)
963 .filter_map(|(parameter, argument)| {
964 let name = parameter.get_variable_name().cloned().unwrap_or("_".into());
965
966 // An argument can be inlined if it is only used once (stored in
967 // the `InlineFunction` structure), and it is pure. Sometime impure
968 // arguments can be inlined, but for simplicity we avoid inlining
969 // all impure arguments for now. This heuristic can be improved
970 // later.
971 if inlinable_parameters.contains(&name)
972 && argument.value.is_pure_value_constructor()
973 {
974 _ = inline.insert(name, argument.value);
975 return None;
976 }
977
978 let type_ = argument.value.type_();
979
980 // Register the variable in scope, so that it is renamed if
981 // necessary.
982 let name = self.define_variable(name);
983
984 // Otherwise, we make an assignment which assigns the value of
985 // the argument to the correct parameter name.
986 Some(Statement::Assignment(Box::new(Assignment {
987 location: BLANK_LOCATION,
988 value: argument.value,
989 pattern: TypedPattern::Variable {
990 location: BLANK_LOCATION,
991 name: name.clone(),
992 type_: type_.clone(),
993 origin: VariableOrigin::generated(),
994 },
995 kind: AssignmentKind::Generated,
996 compiled_case: CompiledCase::simple_variable_assignment(name, type_),
997 annotation: None,
998 })))
999 })
1000 .collect_vec();
1001
1002 // If we are performing inlining within an already inlined function, there
1003 // might be inlinable variables in the outer scope. However, these cannot be
1004 // inlined inside a nested function, so they are saved and restored afterwards.
1005 let inline_variables = std::mem::replace(&mut self.inline_variables, inline);
1006 let position = self.position;
1007 self.position = Position::InlinedFunction;
1008 let variables = self.renamed_variables.clone();
1009
1010 // Perform inlining on each of the statements in this function's body,
1011 // potentially inlining parameters and function calls inside this function.
1012 statements.extend(body.into_iter().map(|statement| self.statement(statement)));
1013
1014 // Restore scope
1015 self.inline_variables = inline_variables;
1016 self.position = position;
1017 self.renamed_variables = variables;
1018
1019 // We try to expand this block, so a function which is inlined as a
1020 // single expression does not get wrapped unnecessarily
1021 expand_block(TypedExpr::Block {
1022 location: BLANK_LOCATION,
1023 statements: statements
1024 .try_into()
1025 .expect("Type checking ensures there is at least one statement"),
1026 })
1027 }
1028
1029 fn pipeline(
1030 &mut self,
1031 location: SrcSpan,
1032 first_value: TypedPipelineAssignment,
1033 assignments: Vec<(TypedPipelineAssignment, PipelineAssignmentKind)>,
1034 finally: Box<TypedExpr>,
1035 finally_kind: PipelineAssignmentKind,
1036 ) -> TypedExpr {
1037 let first_value = self.pipeline_assignment(first_value);
1038 let assignments = assignments
1039 .into_iter()
1040 .map(|(assignment, kind)| (self.pipeline_assignment(assignment), kind))
1041 .collect();
1042 let finally = self.boxed_expression(finally);
1043
1044 TypedExpr::Pipeline {
1045 location,
1046 first_value,
1047 assignments,
1048 finally,
1049 finally_kind,
1050 }
1051 }
1052
1053 fn pipeline_assignment(
1054 &mut self,
1055 assignment: TypedPipelineAssignment,
1056 ) -> TypedPipelineAssignment {
1057 let TypedPipelineAssignment {
1058 location,
1059 name,
1060 value,
1061 } = assignment;
1062
1063 TypedPipelineAssignment {
1064 location,
1065 name,
1066 value: self.boxed_expression(value),
1067 }
1068 }
1069
1070 fn bit_array(
1071 &mut self,
1072 location: SrcSpan,
1073 type_: Arc<Type>,
1074 segments: Vec<TypedExprBitArraySegment>,
1075 ) -> TypedExpr {
1076 let segments = segments
1077 .into_iter()
1078 .map(|segment| self.bit_array_segment(segment, Self::expression))
1079 .collect();
1080
1081 TypedExpr::BitArray {
1082 location,
1083 type_,
1084 segments,
1085 }
1086 }
1087
1088 fn bit_array_segment<Value>(
1089 &mut self,
1090 segment: BitArraySegment<Value, Arc<Type>>,
1091 function: fn(&mut Self, Value) -> Value,
1092 ) -> BitArraySegment<Value, Arc<Type>> {
1093 let BitArraySegment {
1094 location,
1095 value,
1096 options,
1097 type_,
1098 } = segment;
1099
1100 BitArraySegment {
1101 location,
1102 value: Box::new(function(self, *value)),
1103 options: options
1104 .into_iter()
1105 .map(|option| self.bit_array_option(option, function))
1106 .collect(),
1107 type_,
1108 }
1109 }
1110
1111 fn bit_array_option<Value>(
1112 &mut self,
1113 option: BitArrayOption<Value>,
1114 function: fn(&mut Self, Value) -> Value,
1115 ) -> BitArrayOption<Value> {
1116 match option {
1117 BitArrayOption::Bytes { .. }
1118 | BitArrayOption::Int { .. }
1119 | BitArrayOption::Float { .. }
1120 | BitArrayOption::Bits { .. }
1121 | BitArrayOption::Utf8 { .. }
1122 | BitArrayOption::Utf16 { .. }
1123 | BitArrayOption::Utf32 { .. }
1124 | BitArrayOption::Utf8Codepoint { .. }
1125 | BitArrayOption::Utf16Codepoint { .. }
1126 | BitArrayOption::Utf32Codepoint { .. }
1127 | BitArrayOption::Signed { .. }
1128 | BitArrayOption::Unsigned { .. }
1129 | BitArrayOption::Big { .. }
1130 | BitArrayOption::Little { .. }
1131 | BitArrayOption::Native { .. }
1132 | BitArrayOption::Unit { .. } => option,
1133 BitArrayOption::Size {
1134 location,
1135 value,
1136 short_form,
1137 } => BitArrayOption::Size {
1138 location,
1139 value: Box::new(function(self, *value)),
1140 short_form,
1141 },
1142 }
1143 }
1144
1145 fn case(
1146 &mut self,
1147 location: SrcSpan,
1148 type_: Arc<Type>,
1149 subjects: Vec<TypedExpr>,
1150 clauses: Vec<TypedClause>,
1151 compiled_case: CompiledCase,
1152 ) -> TypedExpr {
1153 let subjects = self.expressions(subjects);
1154 let clauses = clauses
1155 .into_iter()
1156 .map(|clause| self.case_clause(clause))
1157 .collect();
1158
1159 // Since JavaScript code generation uses the decision tree to generate
1160 // code for `case` expressions, we need to rename the variables bound
1161 // in the decision tree too. Because we have already renamed the variables
1162 // in the pattern, we can simply look up the rebound names.
1163 let compiled_case = CompiledCase {
1164 tree: self.decision(compiled_case.tree),
1165 subject_variables: compiled_case.subject_variables,
1166 };
1167
1168 TypedExpr::Case {
1169 location,
1170 type_,
1171 subjects,
1172 clauses,
1173 compiled_case,
1174 }
1175 }
1176
1177 fn case_clause(&mut self, clause: TypedClause) -> TypedClause {
1178 let Clause {
1179 location,
1180 pattern,
1181 alternative_patterns,
1182 guard,
1183 then,
1184 } = clause;
1185
1186 let pattern = pattern
1187 .into_iter()
1188 .map(|pattern| self.register_pattern_variables(pattern))
1189 .collect();
1190
1191 let alternative_patterns = alternative_patterns
1192 .into_iter()
1193 .map(|patterns| {
1194 patterns
1195 .into_iter()
1196 .map(|pattern| self.register_pattern_variables(pattern))
1197 .collect()
1198 })
1199 .collect();
1200
1201 let then = self.expression(then);
1202
1203 Clause {
1204 location,
1205 pattern,
1206 alternative_patterns,
1207 guard,
1208 then,
1209 }
1210 }
1211
1212 fn decision(&self, decision: Decision) -> Decision {
1213 match decision {
1214 Decision::Run { body } => Decision::Run {
1215 body: self.case_body(body),
1216 },
1217 Decision::Guard {
1218 guard,
1219 if_true,
1220 if_false,
1221 } => Decision::Guard {
1222 guard,
1223 if_true: self.case_body(if_true),
1224 if_false: Box::new(self.decision(*if_false)),
1225 },
1226 Decision::Switch {
1227 var,
1228 choices,
1229 fallback,
1230 fallback_check,
1231 } => Decision::Switch {
1232 var,
1233 choices: choices
1234 .into_iter()
1235 .map(|(check, decision)| (check, self.decision(decision)))
1236 .collect(),
1237 fallback: Box::new(self.decision(*fallback)),
1238 fallback_check,
1239 },
1240 Decision::Fail => Decision::Fail,
1241 }
1242 }
1243
1244 fn case_body(&self, body: Body) -> Body {
1245 let Body {
1246 bindings,
1247 clause_index,
1248 } = body;
1249
1250 let bindings = bindings
1251 .into_iter()
1252 // We do this after renaming the variables in the pattern, so we can
1253 // just lookup the new name, rather than renaming again.
1254 .map(|(name, value)| (self.variable_name(name), value))
1255 .collect();
1256
1257 Body {
1258 bindings,
1259 clause_index,
1260 }
1261 }
1262}
1263
1264fn find_inlinable_parameters(parameters: &[TypedArg], body: &[TypedStatement]) -> Vec<EcoString> {
1265 let mut parameter_map = HashMap::new();
1266 for parameter in parameters {
1267 let (name, location) = match ¶meter.names {
1268 ArgNames::Discard { .. } | ArgNames::LabelledDiscard { .. } => continue,
1269 ArgNames::Named { name, location }
1270 | ArgNames::NamedLabelled {
1271 name,
1272 name_location: location,
1273 ..
1274 } => (name, location),
1275 };
1276 _ = parameter_map.insert((name.clone(), *location), false);
1277 }
1278
1279 let mut finder = FindInlinableParameters {
1280 parameters: parameter_map,
1281 position: FunctionPosition::Body,
1282 };
1283 for statement in body {
1284 finder.visit_typed_statement(statement);
1285 }
1286
1287 // Inlinable parameters are those that are used exactly once. Any parameters
1288 // used more than once will be removed from this map and so will not be
1289 // considered inlinable.
1290 finder
1291 .parameters
1292 .into_iter()
1293 .filter_map(|((name, _), used)| used.then_some(name))
1294 .collect()
1295}
1296
1297/// A struct for finding the inlinable parameters of an anonymous function. Since
1298/// we want to inline all anonymous functions, not just a subset of them like we
1299/// do with regular functions, this must be implemented slightly differently, but
1300/// it means we can take advantage of the AST visitor, since we don't need to
1301/// transform the anonymous function into an intermediate representation.
1302struct FindInlinableParameters {
1303 parameters: HashMap<(EcoString, SrcSpan), bool>,
1304 position: FunctionPosition,
1305}
1306
1307#[derive(Debug, Clone, Copy)]
1308enum FunctionPosition {
1309 Body,
1310 NestedFunction,
1311}
1312
1313impl FindInlinableParameters {
1314 fn register_reference(&mut self, name: &EcoString, location: SrcSpan) {
1315 let key = (name.clone(), location);
1316
1317 match self.position {
1318 FunctionPosition::Body => {}
1319 // We don't inline any parameters which are referenced in nested
1320 // anonymous function, as our system for inlining parameters cannot
1321 // properly handle that case; it requires more complex rewriting of
1322 // the code in some cases.
1323 FunctionPosition::NestedFunction => {
1324 _ = self.parameters.remove(&key);
1325 return;
1326 }
1327 }
1328
1329 match self.parameters.get_mut(&key) {
1330 Some(true) => _ = self.parameters.remove(&key),
1331 Some(used @ false) => {
1332 *used = true;
1333 }
1334 None => {}
1335 }
1336 }
1337}
1338
1339impl<'ast> Visit<'ast> for FindInlinableParameters {
1340 fn visit_typed_expr_var(
1341 &mut self,
1342 _location: &'ast SrcSpan,
1343 constructor: &'ast ValueConstructor,
1344 name: &'ast EcoString,
1345 ) {
1346 if let ValueConstructorVariant::LocalVariable { location, .. } = constructor.variant {
1347 self.register_reference(name, location);
1348 }
1349 }
1350
1351 fn visit_typed_clause_guard_var(
1352 &mut self,
1353 _location: &'ast SrcSpan,
1354 name: &'ast EcoString,
1355 _type_: &'ast Arc<Type>,
1356 location: &'ast SrcSpan,
1357 _origin: &'ast VariableOrigin,
1358 ) {
1359 self.register_reference(name, *location);
1360 }
1361
1362 fn visit_typed_bit_array_size_variable(
1363 &mut self,
1364 _location: &'ast SrcSpan,
1365 name: &'ast EcoString,
1366 constructor: &'ast Option<Box<ValueConstructor>>,
1367 _type_: &'ast Arc<Type>,
1368 ) {
1369 let variant = match constructor {
1370 Some(constructor) => &constructor.variant,
1371 None => return,
1372 };
1373 if let ValueConstructorVariant::LocalVariable { location, .. } = variant {
1374 self.register_reference(name, *location);
1375 }
1376 }
1377
1378 fn visit_typed_expr_fn(
1379 &mut self,
1380 location: &'ast SrcSpan,
1381 type_: &'ast Arc<Type>,
1382 kind: &'ast FunctionLiteralKind,
1383 args: &'ast [TypedArg],
1384 body: &'ast Vec1<TypedStatement>,
1385 return_annotation: &'ast Option<ast::TypeAst>,
1386 ) {
1387 let previous_position = self.position;
1388 self.position = FunctionPosition::NestedFunction;
1389
1390 ast::visit::visit_typed_expr_fn(self, location, type_, kind, args, body, return_annotation);
1391
1392 self.position = previous_position;
1393 }
1394}
1395
1396/// Removes any blocks which are acting as brackets (they hold a single expression)
1397fn expand_block(expression: TypedExpr) -> TypedExpr {
1398 match expression {
1399 TypedExpr::Block {
1400 location,
1401 statements,
1402 } if statements.len() == 1 => {
1403 let (first, _rest) = statements.split_off_first();
1404
1405 match first {
1406 // If this is several blocks inside each other, we want to
1407 // expand them all.
1408 Statement::Expression(inner) => expand_block(inner),
1409 Statement::Assignment(_) | Statement::Use(_) | Statement::Assert(_) => {
1410 TypedExpr::Block {
1411 location,
1412 statements: Vec1::new(first),
1413 }
1414 }
1415 }
1416 }
1417 TypedExpr::Int { .. }
1418 | TypedExpr::Float { .. }
1419 | TypedExpr::String { .. }
1420 | TypedExpr::Block { .. }
1421 | TypedExpr::Pipeline { .. }
1422 | TypedExpr::Var { .. }
1423 | TypedExpr::Fn { .. }
1424 | TypedExpr::List { .. }
1425 | TypedExpr::Call { .. }
1426 | TypedExpr::BinOp { .. }
1427 | TypedExpr::Case { .. }
1428 | TypedExpr::RecordAccess { .. }
1429 | TypedExpr::PositionalAccess { .. }
1430 | TypedExpr::ModuleSelect { .. }
1431 | TypedExpr::Tuple { .. }
1432 | TypedExpr::TupleIndex { .. }
1433 | TypedExpr::Todo { .. }
1434 | TypedExpr::Panic { .. }
1435 | TypedExpr::Echo { .. }
1436 | TypedExpr::BitArray { .. }
1437 | TypedExpr::RecordUpdate { .. }
1438 | TypedExpr::NegateBool { .. }
1439 | TypedExpr::NegateInt { .. }
1440 | TypedExpr::Invalid { .. } => expression,
1441 }
1442}
1443
1444/// Converts a function from the Gleam AST into a special "inlinable function",
1445/// which is a simplified version, containing just enough information for us to
1446/// perform inlining, while keeping the cache files to a minimum size.
1447///
1448/// This function also determines whether a function is inlinable. Currently this
1449/// just checks it against a list of stdlib functions we want to prioritise
1450/// inlining, but later it will be changed to a more complicated heuristic.
1451///
1452pub fn function_to_inlinable(
1453 package: &str,
1454 module: &str,
1455 function: &TypedFunction,
1456) -> Option<InlinableFunction> {
1457 let (_, name) = function.name.as_ref()?;
1458
1459 if !is_inlinable(package, module, name) {
1460 return None;
1461 }
1462
1463 let parameters = function
1464 .arguments
1465 .iter()
1466 .map(|argument| match &argument.names {
1467 ArgNames::Discard { name, .. } | ArgNames::Named { name, .. } => InlinableParameter {
1468 label: None,
1469 name: name.clone(),
1470 },
1471 ArgNames::LabelledDiscard { label, name, .. }
1472 | ArgNames::NamedLabelled { label, name, .. } => InlinableParameter {
1473 label: Some(label.clone()),
1474 name: name.clone(),
1475 },
1476 })
1477 .collect();
1478
1479 let mut converter = FunctionToInlinable::new(&function.arguments);
1480
1481 let body = function
1482 .body
1483 .iter()
1484 .map(|statement| converter.statement(statement))
1485 .collect::<Option<_>>()?;
1486
1487 // Figure out which parameters can be inlined within the body of this function.
1488 // When we inline a function, we convert it to a block with assignments for
1489 // the parameters. Then, if those parameters contain no side effects and are
1490 // only referenced once within the body, they can be inlined into the place
1491 // they are referenced.
1492 //
1493 // This code checks for the parameters which are used exactly once, which
1494 // can then be inlined. We can't inline parameters which are never used, as
1495 // there is nowhere to inline them to, so it doesn't make sense. We still
1496 // need to evaluate them though, as there could be side effects caused by
1497 // the values passed to them.
1498 let inlinable_parameters = converter
1499 .parameter_references
1500 .into_iter()
1501 .filter_map(|((name, _), used)| used.then_some(name))
1502 .collect();
1503
1504 Some(InlinableFunction {
1505 parameters,
1506 body,
1507 inlinable_parameters,
1508 })
1509}
1510
1511/// The heuristic to determine whether a function is inlinable. For now, this
1512/// just checks against a list of standard library functions.
1513fn is_inlinable(package: &str, module: &str, name: &str) -> bool {
1514 // For now we only offer inlining of standard library functions
1515 if package != STDLIB_PACKAGE_NAME {
1516 return false;
1517 }
1518
1519 match (module, name) {
1520 // These are the functions which we currently inline
1521 ("gleam/bool", "guard") => true,
1522 ("gleam/bool", "lazy_guard") => true,
1523 ("gleam/result", "try") => true,
1524 ("gleam/result", "map") => true,
1525 ("gleam/result", "map_error") => true,
1526 // For testing purposes it's useful to have a function which will always
1527 // be inlined, which we can define however we want. We only inline this
1528 // when we are in test mode though, because we wouldn't want this detail
1529 // leaking out into real-world code and causing unexpected behaviour.
1530 ("testing", "always_inline") => cfg!(test),
1531 _ => false,
1532 }
1533}
1534
1535/// Holds state for converting a `TypedFunction` into an `InlinableFunction`.
1536struct FunctionToInlinable {
1537 /// A map of parameters to a boolean of whether they have been used. Since
1538 /// Gleam has variable shadowing, we must also store the definition location
1539 /// of each parameter to ensure that it is not a variable shadowing the parameter
1540 /// name.
1541 /// If a parameter is used more than once, it is removed from the map, so it
1542 /// is no longer tracked as an inlinable parameter.
1543 parameter_references: HashMap<(EcoString, SrcSpan), bool>,
1544}
1545
1546impl FunctionToInlinable {
1547 fn new(arguments: &[TypedArg]) -> Self {
1548 let parameter_references = arguments
1549 .iter()
1550 .filter_map(|argument| {
1551 let (name, location) = match &argument.names {
1552 ArgNames::Discard { .. } | ArgNames::LabelledDiscard { .. } => return None,
1553 ArgNames::Named { name, location } => (name.clone(), *location),
1554 ArgNames::NamedLabelled {
1555 name,
1556 name_location,
1557 ..
1558 } => (name.clone(), *name_location),
1559 };
1560
1561 Some(((name, location), false))
1562 })
1563 .collect();
1564
1565 Self {
1566 parameter_references,
1567 }
1568 }
1569
1570 fn statement(&mut self, statement: &TypedStatement) -> Option<InlinableExpression> {
1571 match statement {
1572 Statement::Expression(expression) => self.expression(expression),
1573 Statement::Assignment(_) | Statement::Use(_) | Statement::Assert(_) => None,
1574 }
1575 }
1576
1577 /// Converts an expression to an `InlinableExpression`. We only convert a
1578 /// small subset of the AST for now, enough to compile our desired inlinable
1579 /// stdlib functions. Anything else returns `None`, indicating a function
1580 /// cannot be inlined.
1581 fn expression(&mut self, expression: &TypedExpr) -> Option<InlinableExpression> {
1582 match expression {
1583 TypedExpr::Case {
1584 subjects,
1585 clauses,
1586 compiled_case,
1587 type_,
1588 ..
1589 } => {
1590 let subjects = subjects
1591 .iter()
1592 .map(|expression| self.expression(expression))
1593 .collect::<Option<_>>()?;
1594 let clauses = clauses
1595 .iter()
1596 .map(|clause| self.clause(clause))
1597 .collect::<Option<_>>()?;
1598
1599 Some(InlinableExpression::Case {
1600 subjects,
1601 clauses,
1602 compiled_case: Box::new(compiled_case.clone()),
1603 type_: self.type_(type_),
1604 })
1605 }
1606 TypedExpr::Var {
1607 constructor, name, ..
1608 } => {
1609 match &constructor.variant {
1610 ValueConstructorVariant::LocalVariable { location, .. } => {
1611 let key = (name.clone(), *location);
1612 match self.parameter_references.get_mut(&key) {
1613 Some(true) => {
1614 _ = self.parameter_references.remove(&key);
1615 }
1616 Some(usage) => *usage = true,
1617 None => {}
1618 }
1619 }
1620 ValueConstructorVariant::ModuleConstant { .. }
1621 | ValueConstructorVariant::ModuleFn { .. }
1622 | ValueConstructorVariant::Record { .. } => {}
1623 }
1624
1625 Some(InlinableExpression::Variable {
1626 name: name.clone(),
1627 constructor: self.value_constructor(constructor)?,
1628 type_: self.type_(&constructor.type_),
1629 })
1630 }
1631 TypedExpr::Call {
1632 fun,
1633 arguments,
1634 type_,
1635 ..
1636 } => {
1637 let function = self.expression(fun)?;
1638 let arguments = arguments
1639 .iter()
1640 .map(|argument| {
1641 Some(InlinableArgument {
1642 label: argument.label.clone(),
1643 value: self.expression(&argument.value)?,
1644 })
1645 })
1646 .collect::<Option<_>>()?;
1647
1648 Some(InlinableExpression::Call {
1649 function: Box::new(function),
1650 arguments,
1651 type_: self.type_(type_),
1652 })
1653 }
1654
1655 TypedExpr::Int { .. }
1656 | TypedExpr::Float { .. }
1657 | TypedExpr::String { .. }
1658 | TypedExpr::Block { .. }
1659 | TypedExpr::Pipeline { .. }
1660 | TypedExpr::Fn { .. }
1661 | TypedExpr::List { .. }
1662 | TypedExpr::BinOp { .. }
1663 | TypedExpr::RecordAccess { .. }
1664 | TypedExpr::PositionalAccess { .. }
1665 | TypedExpr::ModuleSelect { .. }
1666 | TypedExpr::Tuple { .. }
1667 | TypedExpr::TupleIndex { .. }
1668 | TypedExpr::Todo { .. }
1669 | TypedExpr::Panic { .. }
1670 | TypedExpr::Echo { .. }
1671 | TypedExpr::BitArray { .. }
1672 | TypedExpr::RecordUpdate { .. }
1673 | TypedExpr::NegateBool { .. }
1674 | TypedExpr::NegateInt { .. }
1675 | TypedExpr::Invalid { .. } => None,
1676 }
1677 }
1678
1679 fn type_(&self, type_: &Arc<Type>) -> InlinableType {
1680 match collapse_links(type_.clone()).as_ref() {
1681 Type::Fn { arguments, return_ } => InlinableType::Function {
1682 arguments: arguments
1683 .iter()
1684 .map(|argument| self.type_(argument))
1685 .collect(),
1686 return_: Box::new(self.type_(return_)),
1687 },
1688 Type::Named {
1689 module,
1690 name,
1691 arguments,
1692 ..
1693 } if module == PRELUDE_MODULE_NAME => self.prelude_type(name, arguments),
1694 Type::Named { .. } | Type::Var { .. } | Type::Tuple { .. } => InlinableType::Other,
1695 }
1696 }
1697
1698 fn prelude_type(&self, name: &str, arguments: &[Arc<Type>]) -> InlinableType {
1699 match (name, arguments) {
1700 ("BitArray", _) => InlinableType::BitArray,
1701 ("Bool", _) => InlinableType::Bool,
1702 ("Float", _) => InlinableType::Float,
1703 ("Int", _) => InlinableType::Int,
1704 ("List", [element]) => InlinableType::List(Box::new(self.type_(element))),
1705 ("Nil", _) => InlinableType::Nil,
1706 ("Result", [ok, error]) => InlinableType::Result {
1707 ok: Box::new(self.type_(ok)),
1708 error: Box::new(self.type_(error)),
1709 },
1710 ("String", _) => InlinableType::String,
1711 ("UtfCodepoint", _) => InlinableType::UtfCodepoint,
1712 _ => InlinableType::Other,
1713 }
1714 }
1715
1716 fn value_constructor(
1717 &mut self,
1718 constructor: &ValueConstructor,
1719 ) -> Option<InlinableValueConstructor> {
1720 match &constructor.variant {
1721 ValueConstructorVariant::LocalVariable { .. } => {
1722 Some(InlinableValueConstructor::LocalVariable)
1723 }
1724 ValueConstructorVariant::ModuleConstant { .. } => None,
1725 ValueConstructorVariant::ModuleFn { name, module, .. } => {
1726 Some(InlinableValueConstructor::Function {
1727 name: name.clone(),
1728 module: module.clone(),
1729 })
1730 }
1731 ValueConstructorVariant::Record { name, module, .. } => {
1732 Some(InlinableValueConstructor::Record {
1733 name: name.clone(),
1734 module: module.clone(),
1735 })
1736 }
1737 }
1738 }
1739
1740 fn clause(&mut self, clause: &TypedClause) -> Option<InlinableClause> {
1741 let pattern = clause
1742 .pattern
1743 .iter()
1744 .map(Self::pattern)
1745 .collect::<Option<_>>()?;
1746 let body = self.expression(&clause.then)?;
1747 Some(InlinableClause { pattern, body })
1748 }
1749
1750 fn pattern(pattern: &TypedPattern) -> Option<InlinablePattern> {
1751 match pattern {
1752 TypedPattern::Variable { name, .. } => {
1753 Some(InlinablePattern::Variable { name: name.clone() })
1754 }
1755 TypedPattern::Constructor {
1756 name,
1757 arguments,
1758 constructor: Inferred::Known(inferred),
1759 ..
1760 } => {
1761 let arguments = arguments
1762 .iter()
1763 .map(|argument| {
1764 Some(InlinableArgument {
1765 label: argument.label.clone(),
1766 value: Self::pattern(&argument.value)?,
1767 })
1768 })
1769 .collect::<Option<_>>()?;
1770
1771 Some(InlinablePattern::Constructor {
1772 name: name.clone(),
1773 module: inferred.module.clone(),
1774 arguments,
1775 })
1776 }
1777
1778 TypedPattern::Constructor {
1779 constructor: Inferred::Unknown,
1780 ..
1781 } => None,
1782
1783 TypedPattern::Int { .. }
1784 | TypedPattern::Float { .. }
1785 | TypedPattern::String { .. }
1786 | TypedPattern::BitArraySize { .. }
1787 | TypedPattern::Assign { .. }
1788 | TypedPattern::Discard { .. }
1789 | TypedPattern::List { .. }
1790 | TypedPattern::Tuple { .. }
1791 | TypedPattern::BitArray { .. }
1792 | TypedPattern::StringPrefix { .. }
1793 | TypedPattern::Invalid { .. } => None,
1794 }
1795 }
1796}
1797
1798/// A simplified version of a `TypedFunction`.
1799#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
1800pub struct InlinableFunction {
1801 pub parameters: Vec<InlinableParameter>,
1802 pub body: Vec<InlinableExpression>,
1803 /// A list of parameters which are only referenced once and can therefore
1804 /// be inlined within the body of this function.
1805 pub inlinable_parameters: Vec<EcoString>,
1806}
1807
1808/// Location information is not stored for inlinable functions, to reduce cache
1809/// size. The only reason we should need location information is for generating
1810/// code for panicking keywords, like `panic` or `todo`.
1811///
1812/// Those are not supported yet, and when they are they will likely require some
1813/// more thought as to how they are implemented, as inlining a function completely
1814/// changes its location in the codebase.
1815const BLANK_LOCATION: SrcSpan = SrcSpan { start: 0, end: 0 };
1816
1817impl InlinableFunction {
1818 /// Converts an `InlinableFunction` to an anonymous function, which can then
1819 /// be inlined within another function.
1820 fn to_anonymous_function(&self) -> (Vec<TypedArg>, Vec1<TypedStatement>) {
1821 let parameters = self
1822 .parameters
1823 .iter()
1824 .map(|parameter| parameter.to_typed_arg())
1825 .collect();
1826
1827 let body = self
1828 .body
1829 .iter()
1830 .map(|ast| Statement::Expression(ast.to_expression()))
1831 .collect_vec();
1832
1833 (
1834 parameters,
1835 body.try_into()
1836 .expect("Type-checking ensured that the body has at least 1 statement"),
1837 )
1838 }
1839}
1840
1841#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
1842pub enum InlinableExpression {
1843 Case {
1844 subjects: Vec<InlinableExpression>,
1845 clauses: Vec<InlinableClause>,
1846 compiled_case: Box<CompiledCase>,
1847 type_: InlinableType,
1848 },
1849
1850 Variable {
1851 name: EcoString,
1852 constructor: InlinableValueConstructor,
1853 type_: InlinableType,
1854 },
1855
1856 Call {
1857 function: Box<InlinableExpression>,
1858 arguments: Vec<InlinableArgument<InlinableExpression>>,
1859 type_: InlinableType,
1860 },
1861}
1862
1863impl InlinableExpression {
1864 fn to_expression(&self) -> TypedExpr {
1865 match self {
1866 InlinableExpression::Case {
1867 subjects,
1868 clauses,
1869 compiled_case,
1870 type_,
1871 } => TypedExpr::Case {
1872 location: BLANK_LOCATION,
1873 type_: type_.to_type(),
1874 subjects: subjects
1875 .iter()
1876 .map(|subject| subject.to_expression())
1877 .collect(),
1878 clauses: clauses
1879 .iter()
1880 .map(|clause| clause.to_typed_clause())
1881 .collect(),
1882 compiled_case: compiled_case.as_ref().clone(),
1883 },
1884 InlinableExpression::Variable {
1885 name,
1886 constructor,
1887 type_,
1888 } => TypedExpr::Var {
1889 location: BLANK_LOCATION,
1890 constructor: constructor.to_value_constructor(type_.to_type()),
1891 name: name.clone(),
1892 },
1893 InlinableExpression::Call {
1894 function,
1895 arguments,
1896 type_,
1897 } => TypedExpr::Call {
1898 location: BLANK_LOCATION,
1899 type_: type_.to_type(),
1900 fun: Box::new(function.to_expression()),
1901 arguments: arguments
1902 .iter()
1903 .map(|argument| argument.to_call_arg(Self::to_expression))
1904 .collect(),
1905 open_parenthesis: None,
1906 },
1907 }
1908 }
1909}
1910
1911#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
1912pub struct InlinableClause {
1913 pub pattern: Vec<InlinablePattern>,
1914 pub body: InlinableExpression,
1915}
1916
1917impl InlinableClause {
1918 fn to_typed_clause(&self) -> TypedClause {
1919 TypedClause {
1920 location: BLANK_LOCATION,
1921 pattern: self
1922 .pattern
1923 .iter()
1924 .map(|pattern| pattern.to_typed_pattern())
1925 .collect(),
1926 alternative_patterns: Vec::new(),
1927 guard: None,
1928 then: self.body.to_expression(),
1929 }
1930 }
1931}
1932
1933#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
1934pub enum InlinablePattern {
1935 Constructor {
1936 name: EcoString,
1937 module: EcoString,
1938 arguments: Vec<InlinableArgument<InlinablePattern>>,
1939 },
1940
1941 Variable {
1942 name: EcoString,
1943 },
1944}
1945
1946impl InlinablePattern {
1947 fn to_typed_pattern(&self) -> TypedPattern {
1948 match self {
1949 InlinablePattern::Constructor {
1950 name,
1951 module,
1952 arguments,
1953 } => TypedPattern::Constructor {
1954 location: BLANK_LOCATION,
1955 name_location: BLANK_LOCATION,
1956 name: name.clone(),
1957 arguments: arguments
1958 .iter()
1959 .map(|argument| argument.to_call_arg(Self::to_typed_pattern))
1960 .collect(),
1961 module: None,
1962 constructor: Inferred::Known(PatternConstructor {
1963 name: name.clone(),
1964 field_map: None,
1965 documentation: None,
1966 module: module.clone(),
1967 location: BLANK_LOCATION,
1968 constructor_index: 0,
1969 }),
1970 spread: None,
1971 type_: unknown_type(),
1972 },
1973 InlinablePattern::Variable { name } => TypedPattern::Variable {
1974 location: BLANK_LOCATION,
1975 name: name.clone(),
1976 type_: unknown_type(),
1977 origin: VariableOrigin::generated(),
1978 },
1979 }
1980 }
1981}
1982
1983#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
1984pub enum InlinableValueConstructor {
1985 LocalVariable,
1986 Function { name: EcoString, module: EcoString },
1987 Record { name: EcoString, module: EcoString },
1988}
1989
1990impl InlinableValueConstructor {
1991 fn to_value_constructor(&self, type_: Arc<Type>) -> ValueConstructor {
1992 let variant = match self {
1993 InlinableValueConstructor::LocalVariable => ValueConstructorVariant::LocalVariable {
1994 location: BLANK_LOCATION,
1995 origin: VariableOrigin::generated(),
1996 },
1997 InlinableValueConstructor::Function { name, module } => {
1998 ValueConstructorVariant::ModuleFn {
1999 name: name.clone(),
2000 field_map: None,
2001 module: module.clone(),
2002 arity: 0,
2003 location: BLANK_LOCATION,
2004 documentation: None,
2005 implementations: Implementations::supporting_all(),
2006 external_erlang: None,
2007 external_javascript: None,
2008 external_cranelift: None,
2009 purity: Purity::Unknown,
2010 }
2011 }
2012 InlinableValueConstructor::Record { name, module } => ValueConstructorVariant::Record {
2013 name: name.clone(),
2014 arity: 0,
2015 field_map: None,
2016 location: BLANK_LOCATION,
2017 module: module.clone(),
2018 variants_count: 0,
2019 variant_index: 0,
2020 documentation: None,
2021 },
2022 };
2023 ValueConstructor {
2024 publicity: Publicity::Private,
2025 deprecation: Deprecation::NotDeprecated,
2026 variant,
2027 type_,
2028 }
2029 }
2030}
2031
2032#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
2033pub struct InlinableArgument<T> {
2034 pub label: Option<EcoString>,
2035 pub value: T,
2036}
2037
2038impl<T> InlinableArgument<T> {
2039 fn to_call_arg<U, F>(&self, convert_value: F) -> CallArg<U>
2040 where
2041 F: FnOnce(&T) -> U,
2042 {
2043 CallArg {
2044 label: self.label.clone(),
2045 location: BLANK_LOCATION,
2046 value: convert_value(&self.value),
2047 implicit: None,
2048 }
2049 }
2050}
2051
2052#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
2053pub struct InlinableParameter {
2054 pub label: Option<EcoString>,
2055 pub name: EcoString,
2056}
2057
2058impl InlinableParameter {
2059 fn to_typed_arg(&self) -> TypedArg {
2060 let is_discard = self.name.starts_with('_');
2061
2062 let names = match &self.label {
2063 Some(label) if is_discard => ArgNames::LabelledDiscard {
2064 label: label.clone(),
2065 label_location: BLANK_LOCATION,
2066 name: self.name.clone(),
2067 name_location: BLANK_LOCATION,
2068 },
2069 Some(label) => ArgNames::NamedLabelled {
2070 label: label.clone(),
2071 label_location: BLANK_LOCATION,
2072 name: self.name.clone(),
2073 name_location: BLANK_LOCATION,
2074 },
2075 None if is_discard => ArgNames::Discard {
2076 name: self.name.clone(),
2077 location: BLANK_LOCATION,
2078 },
2079 None => ArgNames::Named {
2080 name: self.name.clone(),
2081 location: BLANK_LOCATION,
2082 },
2083 };
2084
2085 TypedArg {
2086 names,
2087 location: BLANK_LOCATION,
2088 annotation: None,
2089 type_: unknown_type(),
2090 }
2091 }
2092}
2093
2094/// A simplified version of `Type`, which only cares about prelude types. Code
2095/// generation needs this type information, as some prelude types are handled
2096/// specially in certain cases. Custom type don't matter though, so they all get
2097/// reduced into a single value, which decreases cache size.
2098#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
2099pub enum InlinableType {
2100 BitArray,
2101 Bool,
2102 Float,
2103 Int,
2104 List(Box<InlinableType>),
2105 Nil,
2106 Result {
2107 ok: Box<InlinableType>,
2108 error: Box<InlinableType>,
2109 },
2110 String,
2111 UtfCodepoint,
2112
2113 Function {
2114 arguments: Vec<InlinableType>,
2115 return_: Box<InlinableType>,
2116 },
2117
2118 Other,
2119}
2120
2121fn unknown_type() -> Arc<Type> {
2122 type_::generic_var(0)
2123}
2124
2125impl InlinableType {
2126 fn to_type(&self) -> Arc<Type> {
2127 match self {
2128 InlinableType::BitArray => type_::bit_array(),
2129 InlinableType::Bool => type_::bool(),
2130 InlinableType::Float => type_::float(),
2131 InlinableType::Int => type_::int(),
2132 InlinableType::List(element) => type_::list(element.to_type()),
2133 InlinableType::Nil => type_::nil(),
2134 InlinableType::Result { ok, error } => type_::result(ok.to_type(), error.to_type()),
2135 InlinableType::String => type_::string(),
2136 InlinableType::UtfCodepoint => type_::utf_codepoint(),
2137
2138 InlinableType::Function { arguments, return_ } => type_::fn_(
2139 arguments.iter().map(Self::to_type).collect(),
2140 return_.to_type(),
2141 ),
2142
2143 // Code generation doesn't care about custom types at all, only
2144 // prelude types are handled specially, so we treat custom types as
2145 // opaque generic type variables.
2146 InlinableType::Other => unknown_type(),
2147 }
2148 }
2149}