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