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